c언어 11052번 카드 구매하기 , 16194번 카드 구매하기 2 (백준)

#include <stdio.h>

int main(void) {
	int n, dp[1001] = {};
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++) scanf("%d", &dp[i]); //입력 받기
		
	for(int i=2; i<=n; i++) {
		int tmp = i/2;
		for(int j=1; j<=tmp; j++) { //최댓값 구하기
			if(dp[j] + dp[i-j] > dp[i])
				dp[i] = dp[j] + dp[i-j];
		}
	} printf("%d", dp[n]); //n개 구매하는 데의 최댓값 출력
}

 

풀이 : 다이나믹 프로그래밍

 

1. n을 입력받습니다

2. dp[]라는 배열에 각각 수를 입력 받습니다.

3. 각 개수마다 최댓값을 하나하나씩 n까지 구해나갑니다.

 

최댓값 구하기

 

n개를 뽑을때의 최대 비용은

 

1개의 최대 비용 + n-1개의 최대 비용

2개의 최대 비용 + n-2개의 최대 비용

3개의 최대 비용 + n-3개의 최대 비용

                          ...

 

중 가장 큰 것이 최대 비용이 됩니다.

 

이를 for문으로 구현 할 수 있습니다.

 

 

이 과정을 dp[n]을 구할 때 까지 반복 한 다음

 

4. dp[n]을 출력하면 됩니다.

 

 

 

 

카드 구매하기 2 의 경우는 최솟값을 구하는 문제이므로

부등호 방향만 바꾸어 주면 됩니다.

 

 

 

 

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

11052번: 카드 구매하기

 

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

16194번: 카드 구매하기 2