[백준/C++]#11052 - 카드 구매하기

풀이

#include <iostream>
using namespace std;

int main() {
	int n;
	int D[1001], p[10001];
	cin >> n;
	for (int i=1; i<=n; i++)	//	개수당 가격 대입
		cin >> p[i];
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=i; j++)
			D[i] = max(D[i],D[i-j]+p[j]);	// 기존 값과 비교해 최댓값을 대입
	}
	cout << D[n];
	return 0;
}

 

개념

다이나믹 프로그래밍 문제

이전의 계산을 다음 계산에서 사용할 수 있는 점은 여전하다.

---

풀이 

n를 가장 비싸게 살 수 있는 금액은 D[n]이다.

D[n]을 구하기 위해서 이전 값을 사용해야 하며, 금액의 크기를 비교해야 할 것이다.

문제를 해결하기 위해 간단한 경우를 보면, n=4일 때 D[4]의 값은

D[3]+p[1]

D[2]+p[2]

D[1]+p[3]

을 비교해서 가장 큰 값이다.

 

그리고 다음 계산인 n=5에서 구한 D[4]의 값이 활용된다.

이러한 계산 과정은 2개의 배열과 이중 반복문을 사용해 해결할 수 있다.

---

+a

 

이 문제는 직접 해결하지 못했다. 다른 방안을 떠올려봤는데, 각 개수만큼 값을 나누는 경우를 생각해보았다.값이 홀수이면 제대로 나눠지지 않을 뿐더러, 실제로는 나눠진 값을 사용하지 않으므로 타당하지 않게 생각된다. 다른 방안을 생각하다가 상당히 애를 먹었다..다이나믹 프로그래밍 구현은 원하는 값을 구하기 위해, 원치않는 상당한 양의 복잡한 계산을 하게된다.

 

 

※문제 내용은 같은데, 이름과 설명이 바뀌었다. 옛날에는 붕어빵문제였다.붕어빵을 가장 비싸게 팔아야하는 문제였는데, 도의적 문제가 있어서 수정된 것 같다.