solved.ac Grand Arena #3

이 문제에서는 각 사이즈별로 구매할 티셔츠 묶음 수와, 구매할 펜 묶음 수를 구해야합니다. 우선, 간단한 펜 묶음의 수 부터 구해봅시다.

펜

펜 묶음을 몇 개 주문할지 구하기 위해서는, $N$개의 펜을 $P$개 단위로 묶어야합니다. 나눗셈을 사용하면, $N$을 $P$로 나눈 몫 $q$와 나머지 $r$을 구할 수 있습니다. 수식으로는 $N \div P = q \cdots r$으로 표현합니다. 이는 펜을 $P$개씩 묶으면 $q$개가 묶이고, $r$개가 남는다는 뜻입니다. 이 $q, r$이 펜을 주문해야하는 묶음 수와, 주문 후 펜을 한 자루씩 주문해야하는 수입니다.

티셔츠

풀이 1

이제 S사이즈의 티셔츠를 몇 묶음 구매해야 하는지 계산합시다.

$S$ 사이즈의 티셔츠를 $T$장 단위로 묶기 위해서 나눗셈을 씁니다. $S$를 $T$로 나눈 몫과 나머지를 각각 $q, r$라고 표현합시다. $(S \div T = q \cdots r)$

• $r = 0$인 경우에, 딱 $q$ 묶음을 주문하면 티셔츠를 남김 없이 나누어 줄 수 있습니다. 이 때의 답은 $q$입니다.

• $r > 0$인 경우에, $q$묶음을 주문하면 추가로 $r$개의 티셔츠를 주문해야 합니다. 티셔츠는 한 장씩 따로 주문할 수는 없으므로, 한 묶음을 더 주문해야하고 이 때의 답은 $q+1$입니다.

각각의 언어로는 다음과 같이 구현할 수 있습니다. 변수명은 각각 S, T 이고 결과는 res 입니다.

C++

int q = S / T, r = S % T;
int res = q + (r > 0 ? 1 : 0);

Python

q, r = S // T, S % T
res = q + (1 if r > 0 else 0)

Rust

let q = S / T;
let r = S % T;
let res = q + if r > 0 { 1 } else { 0 };

풀이 2

if 문을 사용하지 않고도 코드를 작성할 수 있습니다. 우선, 다음과 같은 기호를 쓰겠습니다.

• $\frac{a}{b}$: $a$를 $b$로 나눈 값입니다.
  • 이 글에서는 정수 나눗셈이 아니라, 실수 사이의 나눗셈을 사용합니다.
  • 예를 들어, $\frac{9}{5} = 1.8$입니다.
• $\left \lfloor x \right \rfloor, \left \lceil x \right \rceil$: 각각 $x$보다 작은 최대의 정수, $x$보다 큰 최소의 정수를 의미합니다.
  • 예를 들어, $\lfloor 3 \rfloor = 3, \lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$입니다.
  • 예를 들어, $\lceil 3 \rceil = 3, \lceil 3.14 \rceil = 4, \lceil 4 \rceil = 4$입니다.
  • $x$가 정수일 때는, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor$입니다.
  • $x$가 정수가 아닐 때는, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor + 1$입니다.

우리가 정수 나눗셈에서 구하는 $S$를 $T$로 나눈 몫은, $\left\lfloor \frac{S}{T} \right \rfloor$입니다. $S$를 $T$로 나눈 후에, $T$개씩 묶지 못하는 소수 부분을 없애줍니다. 하지만, 이 문제에서 구해야 할 것은 $\left \lceil \frac{S}{T} \right \rceil$입니다. 소수부분이 남더라도, 그 부분을 $1$개의 묶음으로 생각해줘야합니다.

이제, 다음을 증명합시다. $0$ 이상인 정수 $S$와, $1$ 이상인 정수 $T$에 대해, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac{S+T-1}{T} \right\rfloor$입니다.

• $S$가 $T$의 배수인 경우에는, $\left\lceil \frac{S}{T} \right\rceil = \frac{S}{T}$ 이고, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S}{T} + \frac{T-1}{T} \right\rfloor$입니다. $\frac{S}{T}$는 정수이고, $\frac{T-1}{T}$는 $1$보다 작은 부분이기 때문에, 무시되어서, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \frac{S}{T}$입니다.

• $S$가 $T$의 배수가 아닌 경우에는, $\frac{S}{T}$가 정수가 아니기 때문에, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac S T \right\rfloor + 1$입니다. 또한, $S$에서 나머지가 $1$개 이상 남기 때문에, $S-1$을 $T$로 나누어도 몫이 동일합니다. 즉, $\left \lfloor \frac{S-1}{T} \right \rfloor = \left \lfloor \frac{S}{T} \right\rfloor$입니다. $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S-1}{T} + \frac{T}{T} \right\rfloor = \left\lfloor \frac{S}{T} \right \rfloor + 1 = \left\lceil \frac S T \right \rceil$입니다.

이를 이용하면 좀 더 간단하게 코드를 작성할 수 있습니다. 아래는 각 언어로 작성된 모범답안입니다.

코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> sizes(6);
    for (int &size : sizes)
        cin >> size;
    int T, P;
    cin >> T >> P;
    int sumv = 0;
    for (int size : sizes)
        sumv += (size + T - 1) / T;
    cout << sumv << endl;
    cout << N / P << " " << N % P << endl;
}

코드 (Python)

def main():
    N = int(input())
    sizes = list(map(int, input().split()))
    T, P = map(int, input().split())
    print(sum((size + T - 1) // T for size in sizes))
    print(N // P, N % P)


if __name__ == '__main__':
    main()

코드 (Rust)

use std::io::*;

fn main() {
    let n = read_vec()[0];
    let sizes = read_vec();
    let (t, p) = {
        let v = read_vec();
        (v[0], v[1])
    };

    println!("{}", sizes.iter().map(|x| (x + t - 1) / t).sum::<u32>());
    println!("{} {}", n / p, n % p);
}

fn read_vec() -> Vec<u32> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}