C++로 합이 k가 되는 최소 동전 개수 구하기

문제 설명

두 개의 정수 n과 k가 주어졌다고 가정해 봅시다. 우리는 가치가 1부터 n까지인 동전을 무한히 많이 가지고 있으며, 이 동전들을 조합하여 합이 정확히 k가 되도록 만들려고 합니다. 같은 가치의 동전은 여러 번 사용할 수 있습니다. 목표는 합이 k가 되기 위해 필요한 최소 동전 개수를 구하는 것입니다.

예를 들어 n = 6, k = 16이 입력으로 주어진 경우를 생각해 보겠습니다. 6짜리 동전 두 개와 4짜리 동전 하나, 즉 (2 × 6) + 4 = 16이 되므로 총 3개의 동전이 필요합니다. 따라서 출력은 3이 됩니다.

접근 방법

동전의 가치는 최대 n이므로, 가능한 한 가장 큰 가치의 동전(n)을 최대한 많이 사용하는 것이 동전 개수를 줄이는 핵심 전략입니다. 결국 필요한 최소 동전 개수는 k를 n으로 나눈 값을 올림(ceil)한 값과 같습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

c := (n + k - 1) / n
return c

여기서 (n + k - 1) / n은 정수 나눗셈을 활용한 올림 나눗셈 기법입니다. C++에서 정수형끼리 나누면 소수점 이하가 버려지기 때문에, 분자에 (n - 1)을 미리 더해 올림 효과를 얻을 수 있습니다.

예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include<bits/stdc++.h>
using namespace std;

int solve(int n, int k){
   int c=(n+k-1)/n;
   return c;
}
int main(){
   int n = 6;
   int k = 16;
   cout << solve(n, k) << endl;
}

입력

6, 16