이번에 풀어본 문제는
백준 11052번 카드 구매하기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int [] p = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; ++i)
        {
            p[i] = Integer.parseInt(st.nextToken());
        }

        int [] dp = new int[N+1];
        dp[1] = p[1];

        for(int i = 2; i <= N; ++i)
        {
            dp[i] = p[i];

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

📝 풀이

N개의 카드를 구매하는 가장 비싼 비용을 출력하는 문제입니다.
N개의 카드를 구매하는 방법으로 N개가 모두 들은 카드팩 한 묶음을 구매하는 방법과, i개가 들은 카드팩과 N-i개가 들은 카드팩, 또는 더 나누어서 구매할 수 있는 다양한 방법이 존재합니다. 하지만 이 방법을 모두 고려하는 것은 많이 비효율적이기 때문에 dp를 활용해보았습니다. dp배열은, 각 인덱스에 해당하는 개수의 카드를 구매하는 최대비용이 담기게 됩니다.
반복문 내부를 보시면, 먼저 i개의 카드를 한번에 구매하는 비용으로 초기화 시킨 후, j 값을 i/2까지 증가시키며 카드팩을 나누어 구매하는 방법과 최댓값을 비교해줍니다. 이전 과정을 통해 dp배열에는 최적화된 값이 들어있기 때문에, 더 작은 조각으로 나누는 방법은 고려하지 않아도 되며, 두 묶음으로 나누어 비교할 수 있게됩니다.
i/2까지만 반복하는 이유는, (dp[x] + dp[y]) 는 (dp[y] + dp[x])와 같기 때문에, 절반만 비교해주어도 동일한 값을 얻어낼 수 있기 때문입니다.
최종적으로 dp[N]값을 출력해주면 됩니다.

📜 후기

dp 유형에 익숙해지기 위해 하루 3문제정도 풀어보고 있습니다. 그래도 조금씩 실력이 느는것 같긴 하지만 매 문제마다 새로운 기분이라.. 좀 더 노력해봐야겠어요 ㅠ