DP에서 1차원 배열을 쓰면 안 되는 경우

예시

백준 1493번 기타리스트
https://www.acmicpc.net/problem/1495

문제 코드

1차원 배열로

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int s = scan.nextInt();
        int m = scan.nextInt();

        int[] v = new int[n];

        for(int i = 0; i < n; i++) {
            v[i] = scan.nextInt();
        }

        int[] dp = new int[m+1];

        Arrays.fill(dp, -1);
        //첫곡
        if(s+v[0]<=m) dp[s+v[0]] = 0;
        if(s-v[0]>=0) dp[s-v[0]] = 0;

        boolean stop = true;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= m; j++) {
                if(dp[j]==i-1) {
                    if(j+v[i]<=m) dp[j+v[i]] = i;
                    if(j-v[i]>=0) dp[j-v[i]] = i;
                    stop = false;
                }
            }
            if(stop) {
                System.out.println("-1");
                return;
            } else {
                stop = true;
            }
        }

        for(int j = m; j >= 0; j--) {
            if(dp[j]==n-1) {
                System.out.println(j);
                return;
            }
        }
    }
}

dp에 노래 번호를 저장하고 갱신하는 방식으로 구현
배열에서 값이 이전 노래인 i-1을 찾아서 -> 새로운 인덱스에 i 저장

반례

2 1 4
1 2

i-1 값을 가진 인덱스를 모두 탐색해야 하는데, i-1 값을 가진 인덱스가 탐색하기 전에 i 값으로 바뀔 수 있음

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int s = scan.nextInt();
        int m = scan.nextInt();

        int[] v = new int[n+1];

        for(int i = 1; i <= n; i++) {
            v[i] = scan.nextInt();
        }

        scan.close();

        boolean[][] dp = new boolean[m+1][n+1];
        dp[s][0] = true;

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(dp[j][i-1]) {
                    if(j+v[i]<=m) dp[j+v[i]][i] = true;
                    if(j-v[i]>=0) dp[j-v[i]][i] = true;
                }
            }
        }

        for(int j = m; j >= 0; j--) {
            if(dp[j][n]) {
                System.out.println(j);
                return;
            }
        }
        System.out.println("-1");
    }
}