[백준 / C++] 11052번: 카드 구매하기 (dp)

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

난이도: solved.ac 실버 1

 

알고리즘 분류

다이나믹 프로그래밍 (dp)

 

접근 방법 및 구현

1개의 카드부터 시작해 N개의 카드까지 차례로 구매하는 데 필요한 최대 금액을 계산한다.

계산한 값은 배열 P에 저장했다.

최대 금액을 계산하는 방법은 간단하다.

i개의 카드를 살 때 최대 금액을 계산한다고 해보자. 이때 1개부터 i - 1개의 카드를 살 때의 최대 금액은 이미 알고 있다고 하자.  i개의 카드를 사는 방법은 다음과 같다.

 

1개를 사는 최대 가격과 i - 1개를 사는 최대 가격의 합

2개를 사는 최대 가격과 i - 2개를 사는 최대 가격의 합

...

i / 2개를 사는 최대 가격과 i / 2개를 사는 최대 가격의 합

(i가 홀수이든 짝수든 상관 없음)

 

이 중에서 가장 큰 값이 i개의 카드를 사는 최대 가격이 된다.

 

위 과정을 i = N까지 진행해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j;
	int P[1001];
	cin >> N;
	for (i = 1; i <= N; i++)
		cin >> P[i];
	for (i = 1; i <= N; i++) {
		int Max = 0;
		for (j = 1; j <= i / 2; j++) {
			int tmp = P[j] + P[i - j];
			if (tmp > Max)
				Max = tmp;
		}
		P[i] = max(P[i], Max);
	}
	cout << P[N];
}

성능