문제 이해 단계
입력값으로 N이 입력된다.
선택할 수 있는 봉지는 3kg와 5kg이다.
이 봉지들을 이용하여 정확히 Nkg을 나눠 담을 때
가장 적은 봉지가 나오게 하는 문제이다.
문제 접근 단계
현재에서 가장 이득이 되는 선택을 하는
그리디로 풀 수도 있지만,
다이나믹 프로그래밍(DP)으로도 풀 수 있다.
왜냐하면, 작은 부분에서의 답이 큰 부분의 답이 되기 때문이다.
N = 15 일 때를 가정해 보자.
15kg는 12 + 3 또는, 10 + 5에서 만들어진 숫자이다.
즉 12,10에서 만들어진 숫자인데,
12와 10은 (9,7), (7,5)에서 만들어진 숫자이다.
이런 식으로 작은 부분의 연산값이 큰 부분의 값이 된다.
이런 특징을 띄고 있기 때문에 DP로 풀 수 있다는 것이다.
N에서 가장 적은 봉지를 구하는 함수를
dp(N)이라고 했을 때 이를 구해보자.
N이라는 숫자를 만들기 이전 단계에서는
분명히 3kg 또는 5kg를 뺀 (N-3), (N-5) 둘 중 하나가 있었을 것이다.
하지만 가장 적은 봉지를 구해야 하기 때문에 dp연산 중 작은 값을 가져야 한다.
즉 해당 문제의 점화식은 dp(N) = min(dp(N-3), (dp(N-5)) 이다.
이제 이를 코드로 구현한 것이 답이 된다.
나머지는 문제 구현 단계에서 서술하겠다.
문제 구현 단계
int dp(int x) {
if (x < 0) return 99998;
if (x == 3 || x == 5) return 1;
if (d[x] != 0) return d[x];
return d[x] = min(dp(x - 3) + 1, dp(x - 5) + 1);
}핵심이 되는 dp함수이다. 매개변수로 N을 받는다.
0보다 작은 값이 들어오면 굉장히 큰 수를 반환하는데,
이는 최솟값을 반환하는 과정에서 이상한 값이 들어오는 것을 방지하기 위해서이다.
d []라는 배열을 만들어 계산 결과를 해당 배열에 저장한다.
인덱스는 N을 뜻한다.
if(d [x]!= 0)를 이용하여 이미 계산했던 배열이라면
그 배열을 바로 반환해 계산시간을 줄인다.
밑에는 전체 코드이다.
#include <iostream>
using namespace std;
int d[5001];
int dp(int x) {
if (x < 0) return 99998;
if (x == 3 || x == 5) return 1;
if (d[x] != 0) return d[x];
return d[x] = min(dp(x - 3) + 1, dp(x - 5) + 1);
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
d[3] = 1;
d[5] = 1;
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
dp(n);
}
if (d[n] >= 6000) cout << "-1";
else cout << d[n];
}초기에 d [3], d [5]를 1로 미리 초기화해 둔다.
그리고 원하는 d [n] 값을 확인하는데 이 값이
5000을 넘는다는 뜻은 9998을 반환했다는 뜻이다.
즉, 정확하게 나눠 담을 수 없다는 뜻이므로
-1을 반환하도록 한다.
시행착오
다이나믹 프로그래밍 알고리즘 공부를 시작했다.
아무리 공부를 해봐도 접근하는 것은 너무 어려운 것 같다.
실버 문제인데도 점화식을 떠올리는 게
너무 어려워서 인터넷을 참고했다.
역시 dp문제는 많이 풀어봐야 할 것 같다.
아직은 dp 식 사고가 어렵다.