https://www.acmicpc.net/problem/11052
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<iostream> using namespace std; int price[10001], memo[10001]; int P(int N) { if (N == 0) return memo[N] = 0; if (N == 1) return memo[N] = price[N]; int k; for (k = 1; k <= N; k++) { if (memo[N] < P(N - k) + price[k]) { memo[N] = P(N - k) + price[k]; } } return memo[N]; } int main() { int N = 0; cin >> N; for (int i = 1; i <= N; i++) { cin >> price[i]; } cout << P(N) << "\n"; return 0; } | cs |
먼저보자 문제는 총 N개의 붕어빵을 팔았을때 얻을 수 있는 최대값을 구하라는 것이다.
정의를 잘 내려야 점화식을 해결할때 큰 도움이 된다.
1. 이를 이용해 붕어빵값의 최대값을 구하는 함수를 P(N)이라고 하자.
P(N)에서 마지막에 올 수 있는 인자의 값은 무엇이 될까?? 모른다... 하지만 !! 어떤값이 올지는 몰라도 가정은 할 수 있다. 문제조건에서 주어진 Price(i)들중에 하나가 올 수있다는 것은 너무나 당연하다. 식으로 나타내면
2. 붕어빵의 최대값을 구하는 함수를 P(N) = ? + price(i) 라고 나타 낼 수 있다. 이렇게 식을 세우면 또하나의 힌트를 얻게된다. N개에서 i개를 판 가격이 price(i)이므로 ?의 개수는 N-i라고 나타낼 수 있다.
그렇다면 N-i개의 최대가격과 Price(i)가 합쳐지면
앞서 말했듯이 문제를 구할 때 정의를 잘 내리면 점화식을 해결할 때 큰 도움이 된다고 했다.
P(N) = N개에서의 최대값 이므로 N-i개에서의 최대값은 P(N-i)로 정의 할 수 있다.
3.점화식 : P(N) = P(N-i) + price(i) 을 구할 수 있다.
위 코드로 점화식을 구현하였다.
최근 덧글