백준-11052번/카드 구매하기

 

최대 지불 금액의 경우의 수를 모두 구해서 비교한다면 시간초과 오류가 발생할 것이다.

따라서 다이나믹 프로그래밍의 절차인 점화식을 만들어서 원하는 값을 구해야 겠다고 생각했다.

 

배열 p ==> i요소의 값은 카드 i개를 구매할때의 가격

배열 dp ==> N개의 카드를 구매할때의 최대금액 저장 배열

 

dp[1](카드 1개를 구매할때의 최대 금액) ==> p[1]

dp[2](카드 2개를 구매할때의 최대 금액) ==> p[1](카드 한장의 금액) + dp[1](카드 한장 살때의 최대금액)과 p[2](카드 2장의 금액) 중의 최대값

dp[3](카드 3개를 구매할때의 최대 금액) ==> p[3](카드 3장 구매할때 가격)과 (dp[2]+p[1]),(dp[1]+p[2]) 중 최대 금액

.

.

.

.

 

이러한 과정으로 점화식을 구할 수 있다.

for(int i=1; i<=n; i++) {
			for(int j=1; j<=i; j++) {
				dp[i]=Math.max(dp[i],dp[i-j]+p[j]);
			}
		}

 

 

<전체 코드>

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		int[] dp = new int[n+1];
		int[] p = new int[n+1];
		for(int i=1; i<=n; i++) {
			p[i]=scanner.nextInt();
		}
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=i; j++) {
				dp[i]=Math.max(dp[i],dp[i-j]+p[j]);
			}
		}
		
		System.out.println(dp[n]);
	}
}