백준(BOJ) 1495: 기타리스트

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

곡=아이템, 볼륨=무게 와 대응된다는것을 눈치채지 못했다.

왜? 0-1배낭문제는 dp의 안에들어가는 것이 보석의 가치이지만 기타리스트 문제에서는 dp안에 들어가는 값을 무엇으로 해주어야 할지 막막했다.

구하라고 하는 것이 최대볼륨인데 볼륨을 그냥 X축으로 사용해 버리리라고는 생각도 못했다.(문제를 정리해 나아가야 한다)


이문제는 점화식이라고 할게 없다. 그저 가로축, 세로축에 각각 어떤소재가 들어가는지 그리고 dp의 각 슬록값이 무엇이 되는지가 더 중요하다.(하지만 최적해를 구성하는데 부분해가 간접적으로는 쓰이고 있다)
점화식보다는 이것들을 파악하는 것이 더 중요한 문제가 있다. 그게 이 문제다. 문제를 정리해 나가야 한다. 


어떻게 해서든, 무슨 수를 써서건 문제를 정리해 가야한다. 그렇다면 문제를 정리해 간다는 것은 무슨 의미인가? 내가 기존에 정리한 문제와 비교해본후에 왜 그런 풀이법이 나와야만 했는지 당위성을 면밀히 파악하는 것이다.

왜 0-1배낭문제에서는 dp의 슬롯에 보석의 무게를 고려한 각 조건값에서의 최대 가치가 들어가고 기타리스트 문제에서는 dp의 각 슬록에 boolean값이 들어가나? 배낭문제에서는 어떠한 보석이건 간에 반드시 포함되어야 하는 보석은 존재하지 않는다. 그리고 배낭문제의 각 dp슬롯은 그 슬롯이 속하는 행의 보석을 포함했는가, 포함하지 않았는가를 말해 주는 것이 아니다. 다만 확실한 것은 그 행의 보석을 넣는 경우와 넣지 않은 경우중 어느것이 최선인가를 비교해 보았다는 것이다.  보석의 포함 여부는 안중에도 없다. 매 슬롯을 채우는 순간마다 그 행의 보석을 넣는 경우와 넣지 않는 경우를 비교하여 최선의 가치값만을 슬롯에 기록한다.

하지만 기타리스트 문제는 다르다. 기타리스트 문제에서는 주워진 곡들이 빠짐없이 플레이 되어야 한다. 이렇게 빠짐없이 플레이 되는 과정에서 각각의 곡들을 +m, -m의 볼륨으로 연주되었는가에 따라 한곡을 연주할 때마다 그경우의 수가 제곱씩 늘어난다. 즉, 이진 트리의 형태인 것이다(물론 볼륨은 0보다 작으면 안되고 m을 초과해서는 안되고 다른 경로를 거치고 있더라도 중간에 같은 볼륨수치가 나올수 있기 때문에 총 볼륨의 경우의 수는 m+1가지로 제안된다). 그 모든 경우를 모두 고려해야 한다. 왜? 모든 곡이 연주되어야 한다는 것에서 각 곡이 +m으로 연주되었는가 -m으로 연주되었는가에 따라 가능한 볼륨의 값이 매 행에거쳐 folllw-up되어야 하기 때문이다. 즉 해당행에서의 true의 개수가 곧 그 이전곡들을 모두 거치면서 그 곡에서 나올수 있는 가능한 모든 볼륨의 경우의 수이다.

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

public class Testing3 {
    public static void solution(int n, int s, int m, int[] arr) {
        boolean[][] dp = new boolean[n + 1][m + 1];
        if (s + arr[1] <= m)
            dp[1][s + arr[1]] = true;
        if (s - arr[1] >= 0)
            dp[1][s - arr[1]] = true;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[i - 1][j]) {
                    if (j + arr[i] <= m) dp[i][j + arr[i]] = true;
                    if (j - arr[i] >= 0) dp[i][j - arr[i]] = true;
                }
            }
        }
        for(int i=m;i>=0;--i){
            if(dp[n][i]){
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        solution(n, s, m, arr);
    }
}