[Java] 11052번: 카드 구매하기 Silver 1

문제 링크

이렇게 생각했다!

DP[i]는 i개 카드를 구매할 수 있는 최대 비용이다.

처음에 DP 배열은 잘 정의했음에도,
그렇다면 앞에서 dp[i]를 결정하는 부분만 집중하면 됐는데,
dp[i]가 뒤에 어떤 영향을 미치는지까지 고려하다보니 오히려 생각이 복잡해졌다..🤮

즉, dp[i]가 어떻게 만들어지는 지만 집중하라는 것이다.

1차 시도

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // Pi 입력 받기
        int[] dp = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
        }

        // dp
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; i * j < N + 1; j++) {
                dp[j * i] = Math.max(dp[j * i], dp[i] * j);
            }
            if (N - i > 0) dp[N] = Math.max(dp[N], dp[i] + dp[N - i]);
            else dp[N] = Math.max(dp[N], dp[i] + dp[i - N]);

        }

        System.out.println(dp[N]);
    }
}

여튼 그래서 30%에서 틀렸다..😥

아까 말한 의미를 다시 생각해보자.

DP[i]가 결정되는 부분에만 집중하라고 했다!

그렇다면 앞에서부터 한 칸씩 완성해갈 수 있지 않을까?
예를 들어
1. 1개 카드를 구매하는 최대 비용은 카드 1개의 구매 비용과 똑같다.
2. 2개 카드를 구매하는 최대 비용은 카드 1개를 두 번 구매한 경우와 2개의 구매 비용 중에서 더 큰 금액이다.
...

이런 식으로 해당 칸을 결정하는 방법은 i보다 적은 개수들로 만드는 경우의 수를 모두 고려해보면 된다!

그걸 for문으로 잘 표현하고, 젤 큰 값으로 갱신하면 되는 것이다!

정답

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // Pi 입력 받기
        int[] dp = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
        }

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

        System.out.println(dp[N]);
    }
}

이렇게 하니 바로 통과했다!