백준 11052(카드 구매하기)

jh Seo·2022년 8월 2일

다이나믹 프로그래밍 백준 한번에 못 푼 문제

백준

목록 보기

35/194

개요

[링크]백준 11052번: 카드 구매하기

입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
출력
첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

접근 방식

처음 시도한 방식
최근에 푼 [동전 2] 방식이 떠올라서,
그대로 풀어보려고, dp[n 번째][지금까지 카드를 선택한 갯수] 이렇게
2차원 배열을 설정해 풀었다.
하지만 dp에 아직 익숙치 않은건지 n이 0이 될 때나, 카드 선택한 갯수가
몇이 되면 return을 뭘 해야할지 몰라서 다른 사람의 풀이를 보며 공부했다.
바텀 업 방식
해결하는데 키 포인트가 되는 점화식은
n번째 카드를 선택했을 때의 구할 수 있는 최대값은,
1부터 n-1값의 범위를 가진 i번째 카드를 선택했을 때
i번째 카드의 값+ n-i번째 카드 선택했을 때의 최대값이다.
코드로 구현하면 이런 식이다.
```
for (int i = 1; i < n; i++)
dp[n] = max(dp[n], arr[i]+dp[n-i]);
```
탑 다운 방식
int solution(int n)
이 재귀 함수의 return값은 n번째 카드를 선택했을 때 최댓값을 return
n이 0이 되면 0번째 카드 선택시 최댓값은 0이므로 0 return

위의 바텀업 방식과 마찬가지로
```
int& ret = dp[n];
for(int i=1;i<=n;i++)
ret = max(ret, arr[i] + solution(n - i));
```
위 식을 이용한다

바텀업 방식 코드

#include<iostream>							
#include<algorithm>

using namespace std;

const int MAX = 1001;
//i번째, amount
int dp[MAX]	,arr[MAX], amount = 0;

//입력받는 함수
void input() {
	cin >> amount;
	for (int i = 1; i <= amount; i++) {
		cin >> arr[i];
	}
}

//dp배열 바텀업 방식으로 쌓고 답 출력하는 함수
void solution() {
	
	for (int i = 1; i <= amount; i++) {
		//각 dp[i]에는 i개들어있는 카드팩 샀을 때의 값어치로 초기화해줌
		dp[i] = arr[i];
		for (int j = 1; j < i; j++) {
			//그후 dp[i]와 
			//1개 들어있는 카드팩을 샀을 때의 최대값부터 i-1개 카드팩을 샀을 때의 최댓값을 구해 비교한다.
			dp[i] = max(dp[i], arr[j]+dp[i-j]);
		}
	}
	//답 출력
	cout << dp[amount];
}

int main() {
	input();
	solution();
}

탑 다운 방식 코드

#include<iostream>							
#include<algorithm>

using namespace std;

const int MAX = 1001;
//i번째, amount
int dp[MAX]	,arr[MAX], amount = 0;

void input() {
	cin >> amount;
	for (int i = 1; i <= amount; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < MAX; i++) {
		dp[i] = -1;
	}
}


//n번째갯수일 때 지불해야할 최댓값
int solution(int n) {
	//0개일땐 지불값이 0
	if (n == 0) return 0 ;
	//ret변수에 dp배열참조
	int& ret = dp[n];
	//이미 구했따면 바로 return
	if (ret != -1) return ret;

	//ret 초기화
	ret = 0;
	//ret값은 각 i개에 대해 카드i개의 가격+ n-i+1개의 카드를 사용했을때 최댓값을 다 비교해서 넣어준다.
	for (int i = 1; i <= n; i++) {
		//i는 몇개의 갯수 인지. n-i+1은 i개의 갯수를 뺐을때의 
		ret = max(ret, arr[i] + solution(n - i));
	}
	return ret;
}


int main() {
	input();
	int Ans = solution(amount);
	cout << Ans;
}