네 개의 숫자 k, n, s, p가 주어진다고 가정해 봅시다. 종이 비행기를 만들려면 직사각형 모양의 종이 조각이 필요하며, 표준 크기의 종이 한 장으로는 s개의 비행기를 만들 수 있습니다.
이제 k명으로 이루어진 그룹이 각자 n개의 비행기를 만들기로 결정했습니다. 이들은 종이 p장이 들어 있는 팩 여러 개를 구매한 뒤, 종이를 서로 나누어 가질 계획입니다. 각 사람은 자신이 만들 n개의 비행기를 완성할 수 있도록 충분한 양의 종이를 받아야 합니다. 그렇다면 최소 몇 개의 팩을 구매해야 할까요?
예를 들어 입력이 k = 5, n = 3, s = 2, p = 3이라면 출력은 4가 됩니다. 각 사람이 비행기 3개를 만들려면 종이 2장이 필요하고(종이 한 장당 비행기 2개 제작 가능), 5명 전체에 필요한 종이는 총 10장입니다. 한 팩에 3장씩 들어 있으므로 4팩을 구매하면 총 12장을 확보할 수 있고, 각 사람에게 2장씩 나누어 줄 수 있기 때문입니다.
풀이 접근 방법
이 문제는 올림 나눗셈(ceiling division)을 두 번 적용하면 간단히 해결할 수 있습니다.
- 사람당 필요한 종이 수: 종이 한 장으로 비행기 s개를 만들 수 있으므로, 비행기 n개를 만드는 데 필요한 종이 수는 ⌈n / s⌉입니다. 정수 연산에서는
(n + s - 1) / s로 올림 나눗셈을 구현할 수 있습니다. - 그룹 전체의 필요 종이 수: 사람당 필요한 종이 수에 인원수 k를 곱합니다.
- 구매해야 할 팩 수: 필요한 총 종이 수를 팩당 장수 p로 나누되, 올림 처리하여 부족함이 없도록 합니다. 즉,
(ans + p - 1) / p를 사용합니다.
ans := k * ((n + s - 1) / s) return (ans + p - 1) / p
C++ 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int k, int n, int s, int p){
int ans = k * ((n + s - 1) / s);
return (ans + p - 1) / p;
}
int main(){
int k = 5;
int n = 3;
int s = 2;
int p = 3;
cout << solve(k, n, s, p) << endl;
}입력
5, 3, 2, 3
출력
4
코드 설명
solve 함수는 먼저 (n + s - 1) / s를 통해 한 사람이 필요한 종이 장수를 올림 나눗셈으로 계산합니다. 이 값에 인원수 k를 곱해 그룹 전체에 필요한 총 종이 수 ans를 구합니다. 마지막으로 (ans + p - 1) / p를 사용해 총 필요 종이 수를 팩 단위로 올림 나눗셈하여, 구매해야 할 최소 팩 수를 반환합니다.
이 방식은 부동소수점 연산 없이 정수 연산만으로 올림 나눗셈을 정확하게 처리할 수 있다는 장점이 있어, 경계값에서도 오류 없이 동작합니다.