Buy a Card

아쉽게 틀린 문제 복기

다이나믹 프로그래밍 문제 풀이 방법

1. 다이나믹 프로그래밍은 작은 문제의 정답이 큰 문제의 정답으로 이어진다.

2. 쪼갤 수 없는 작은 문제로 쪼갠다.

d[n]은 카드n개가 든 카드팩을 사는 최대 지불 비용이다. 이것은 d[n-1] + a[1], d[n-2] + 1[2], ....이 될 수 있다. 이것을 점화식으로 나타내면

d[i] = d[i-j] + a[j], (1<=j<=i)//여기서 코드로 구현할 때 i-j>=0으로 조건을 부여하는 것보다 j범위를 줄 때 j는 i만큼만 증가하기 때문에 1<=j<=i로 해주면 구현이 용이하다.

점화식 도출 성공. 이 점화식에서 모든 (i,j)쌍에 대한 최댓값 구하는 부분 생각 부족. => 대소 비교해서 더 크면 d[i]값을 갱신하면 됨!(이 쉬운 걸 왜 놓쳤을까) d[i]에서 i값에 따라 나오는 모든 경우의 수 값을 저장해야된다고 생각해서 2차원 배열이 필요하다고 생각했고, 그렇다면 d[i][j]가 의미하는 바를 정의하는 데 어려움을 겪었음.

for(int i=2;i<=n;i++) {
			for(int j=1;j<=i;j++) {
				if(d[i] < d[i-j] + a[j]) {
					d[i] = d[i-j] + a[j];
				}
			}
		}