백준 11052 자바 - 카드 구매하기

문제

---

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

11052번: 카드 구매하기

 

 

 

문제해결

---

- dp 배열을 만들고

dp[1] : 카드 1개 사는 최대값

dp[2] : 카드 2개 사는 최대값

....

dp[n] : 카드 n개 사는 최대값을 넣는다

 

- dp[i]를 구하기 위해선 또다시 반복문을 돌며 모든 dp[i-j] + dp[j]의 값중 가장 큰 값을 dp[i]에 넣는다

i가 5일때

dp[5] : 5장 카드 살때

dp[5-1] + dp[1] : 4장 카드 구매하는 최대값 + 1장 카드 구매하는 최대값

dp[5-2] + dp[2] : 3장 카드 구매하는 최대값 + 2장 카드 구매하는 최대값

dp[5-3] + dp[3] : 2장 카드 구매하는 최대값 + 3장 카드 구매하는 최대값

dp[5-4] + dp[4] : 1장 카드 구매하는 최대값 + 4장 카드 구매하는 최대값

반복되는 부분이 있으므로 두번째 반복문은 i/2까지만 돌아도 된다

import java.util.Scanner;

public class B11052_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            //i개가 들은 팩을 살때
            dp[i] = sc.nextInt();
            //반복문을 돌며 모든 dp[i-j] + dp[j] 의 값중 가장 큰 값을 dp에 저장한다
            for (int j = 1; j <= i/2; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + dp[j]);
            }
        }
        System.out.println(dp[n]);
    }
}