백준 1495: 기타리스트

문제

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

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

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

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

---

일전에 풀어본 문제와 비슷해서 무난하게 통과할 수 있었다.

백준 5557: 1학년 [Java]

백준 5557: 1학년 [Java] - 포포

---

DP 문제는 점화식만 잘 세운다면 그 뒤부터는 문제가 없다.
근데 점화식을 생각하는 것이 참 어렵다.
첫 번째 입력을 그림으로 표현해봤다.

예제 입력 1 

3 5 10
5 3 7

예제 출력 1 

10

처음 볼륨은 5로 주어졌다.
따라서 첫 번째 곡에 선택할 수 있는 볼륨은 5 + volume[1] , 5 - volume[1]이다. 
볼륨의 조건(0부터 m까지. 이번 입력에서는 10이다)을 만족시킨다면 dp 배열에 1로 표시한다. dp[1][0] = 1, dp[1][10] = 1

두 번째 곡에 선택 가능한 볼륨은, 이전 첫 번째 볼륨때 dp에 1로 표시해 놓은 인덱스에 volume[2]를 더하고 뺀 값이다.
-3, 3 , 7, 13이 해당하며 이 중 3과 7이 가능하므로 dp[2][3] =1 , dp[2][7] = 1로 기록한다.

마지막 세 번째 곡에서 선택 가능한 볼륨은 바로 이전 두 번째 볼륨때 dp에 1로 표시해 놓은 인덱스에 volume[3]을 더하고 뺀 값이다. dp에 1로 표시한 인덱스는 3과 7이므로 -4, 0, 10, 14가 가능하며 이 중 0, 10이 가능하다.
따라서 dp[3][0] = 1, dp[3][10] = 1로 기록한다.

요약하면

dp[ i ] [ j ] = i번째 곡에서 j 볼륨으로 연주 가능한지 여부로,

N번째 곡일 때 이전 곡인 N-1번째의 볼륨을 확인하고 N번째 곡의 볼륨을 + - 해주면 된다.

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

public class Main {
    static int n, s, m;
    static int[] volume;
    static int[][] dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        volume = new int[n + 1];

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

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

        dp[0][s] = 1;

        //볼륨의 크기는 1~ m까지 가능하다
        int plus, minus = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if(dp[i-1][j] == 1){
                    plus = j + volume[i];
                    minus = j - volume[i];

                    if (0 <= plus && plus <= m)
                    dp[i][plus] = 1;

                    if (0 <= minus && minus <= m)
                    dp[i][minus] = 1;
                }
            }
        }


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

        System.out.println(-1);
    }
}