[백준, 자바] 11052번 - 카드 구매하기

다이나믹 프로그래밍은 너무 어렵다;;
그래도 해야만 하기에 해봐야지.

문제 링크
https://www.acmicpc.net/problem/11052

실패 코드
백준 사이트의 테스트 케이스는 통과했으나, 20% 정도 채점하다가 틀렸습니다 판정받음

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()); // 민규가 사려하는 카드의 개수
        StringTokenizer st = new StringTokenizer(br.readLine()); // 카드 n개가 포함된 카드팩

        // 사려고 하는 개수랑 구입한 카드팩 안의 카드의 개수가 같아야 한다. (많이 사서 버리기 안됨)
        int[] dp = new int[N + 1]; // 0은 내비두고 1부터 N+1까지 채우자.
        int[] cards = new int[N + 1];
        int max = 0;
        
        for(int i = 1; i < dp.length; i++) {
            int cardPackPrice = Integer.parseInt(st.nextToken());
            cards[i] = cardPackPrice;
            
            int price1 = cardPackPrice * (N / i);
            dp[i] = (N % i == 0) ? (price1) : (price1 + (cards[N % i]));
            max = max < dp[i] ? dp[i] : max;
        }
        System.out.println(max);

    }
}

최종 코드(정답)

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

public class Main_11052 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 민규가 사려하는 카드의 개수
        StringTokenizer st = new StringTokenizer(br.readLine()); // 카드 n개가 포함된 카드팩

        // 사려고 하는 개수랑 구입한 카드팩 안의 카드의 개수가 같아야 한다. (많이 사서 버리기 안됨)
        int[] dp = new int[N + 1]; // 0은 내비두고 1부터 N+1까지 채우자.
        int[] cards = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

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

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

다이나믹 프로그래밍은 메모이제이션할 배열이 필수인데, 배열이라고 치면 인덱스 증가할 때마다 각 연산의 최종 결과값을 갱신해서 저장해야 한다. (내가 이해한 걸로는 그렇다)

인덱스 증가할 때마다 최댓값을 저장해야 하는데 나는 그냥 각 인덱스별로 카드값 계산한 걸 저장해서 거기서 최대값을 구하려고 했더니 모든 테스트 통과 못해서 그런 듯 하다.

나중에 다시 또 복습하러 오겠다.