728x90
붕어빵
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 | #include <stdio.h> int boong[1001]; int boo[1001]; int main(void){ int N; scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d", &boo[i]); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++){ if (i <= j) boong[j]= boong[j] > boong[j-i] + boo[i] ? boong[j] : boong[j - i] + boo[i]; } } printf("%d\n", boong[N]); return 0; } | cs |
<문제 푼 요령>
1. 붕어빵을 끊임없이 갱신하면 최대값을 저장한다.
2. 즉 boong[j] = boong[[j-i] + boo[i] 란 현재 i 값어치의 붕어빵을 넣었다고 가정했을때 이전의 값어치의 최대값에서 더하는 값이다. 즉 이전의 저장된 값이랑 이 값을 비교해서 최대값을 저장하다보면 마지막에 최대값만 남게 될 것이다.
728x90
'Algorithm > DP(동적 계획법)' 카테고리의 다른 글
[백준][11057번][DP] 오르막 수 (0) | 2016.04.13 |
---|---|
[백준][10844번][DP] 쉬운 계단 수 (3) | 2016.04.13 |
[백준][11727번][DP] 2xn 타일링 2 (2) | 2016.04.12 |
[백준][11726번][DP] 2xn 타일링 (2) | 2016.04.12 |
[백준][1463번][DP] 1로 만들기 (1) | 2016.04.12 |
댓글