백준 - 1495번(기타리스트)

문제 출처: https://www.acmicpc.net/problem/1495

문제

• Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

• 먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

• 곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

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 reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());    // 곡의 개수
        int S = Integer.parseInt(tokenizer.nextToken());    // 시작 볼륨
        int M = Integer.parseInt(tokenizer.nextToken());    // 최대 볼륨(0 ~ M)

        int[] vol = new int[N + 1];
        tokenizer = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= N; i++) {
            vol[i] = Integer.parseInt(tokenizer.nextToken());
        }

        boolean[][] DP = new boolean[N + 1][M + 1]; // M까지 써야된다.
        DP[0][S] = true;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                if (!DP[i - 1][j]) continue;

                if (j + vol[i] <= M) DP[i][j + vol[i]] = true;

                if (j - vol[i] >= 0) DP[i][j - vol[i]] = true;
            }
        }

        int ans = -1;

        for (int i = M; i >= 0; i--) {
            if (DP[N][i]) {
                ans = i;
                break;
            }
        }

        System.out.println(ans);
    }

}

• DP이다.
• DP는 아직 감이 잘 안온다... 점화식도 그렇고 문제를 푸는 방법도 그렇고...
• 이론적으로는 알고 있는데 아직 문제를 많이 접하지 않아 그런 것 같다.
• 이 문제도 구글링하여 힌트를 얻은 뒤 풀었다.
• 핵심은, 각 문제별로 가능한 모든 볼륨을 살피는 것이었다. 이러한 포인트를 짚을 수 있는 감을 키워야 될 것 같다.