두 개의 숫자 n과 k가 주어진 상황을 생각해 봅시다. 파티에 초대할 친구가 총 n명 있습니다. 아말(Amal)은 종이접기(오리가미) 형태의 초대장을 직접 만들어 전달하려고 합니다.
초대장 한 장을 만들기 위해 필요한 재료는 다음과 같습니다.
- 빨간색 종이 2장
- 초록색 종이 5장
- 파란색 종이 8장
각 색상별 공책은 무한히 많이 구할 수 있지만, 한 권의 공책에는 오직 한 가지 색상의 종이 k장만 들어 있습니다. 이때 아말이 모든 친구 n명에게 초대장을 전달하기 위해 구매해야 하는 최소 공책 수를 구하는 것이 문제입니다.
문제 예시
예를 들어 입력이 n = 3, k = 5라고 해봅시다. 그러면 출력은 10이 됩니다. 그 이유는 다음과 같습니다.
- 빨간색 종이는 총 6장 필요 → 공책 2권
- 초록색 종이는 총 15장 필요 → 공책 3권
- 파란색 종이는 총 24장 필요 → 공책 5권
따라서 전체 공책 수는 2 + 3 + 5 = 10권이 됩니다.
풀이 접근 방법
이 문제의 핵심은 올림 나눗셈(ceiling division)입니다. 필요한 종이 장수를 공책당 종이 수 k로 나눌 때, 나누어떨어지지 않으면 한 권을 더 사야 하기 때문입니다.
정수 연산만으로 올림 나눗셈을 구현하는 일반적인 공식은 다음과 같습니다.
(필요한 장수 + k - 1) / k
이 공식을 세 가지 색상에 각각 적용하면 답을 구할 수 있습니다.
(2 * n + k - 1) / k + (5 * n + k - 1) / k + (8 * n + k - 1) / k
C++ 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int k){
return (2 * n + k - 1) / k + (5 * n + k - 1) / k + (8 * n + k - 1) / k;
}
int main(){
int n = 3;
int k = 5;
cout << solve(n, k) << endl;
}입력
3, 5
출력
10
정리
이 문제는 단순하지만 올림 나눗셈 공식 (a + k - 1) / k를 활용하는 대표적인 예시입니다. 부동소수점 연산 없이 정수 연산만으로 올림 처리를 할 수 있다는 점에서, 코딩 테스트나 알고리즘 문제 풀이에서 자주 등장하는 유용한 기법이니 꼭 기억해 두시기 바랍니다.