[Java] 백준 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이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

풀이

1) 최대 나올 수 있는 볼륨(M)으로 dp를 만든다.

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

2) dp를 -1로 채운다.

이유는 dp에 몇 번째로 나올 수 있는 볼륨인지 저장할 것이기 때문이다.

즉, 0번째에 나올 수 있는 음향을 체크하기 위함이다. -1로 셋팅안해주면 전 볼륨이 0번째에 나올 수 있다는 의미가 된다.

Arrays.fill(dp, -1);

3) 가장 처음에 실행되는 볼륨에 0번째에 나올 수 있는 볼륨이라고 저장해준다.

dp[S] = 0;

4) 결과값을 초기셋팅 한다.

int result = -1;

5) 현재 진행되는 공연 파트(n)에 나올 수 있는 볼륨(m)을 구한다.

dp 배열 전체를 돌려보며 n-1 파트에 나왔던 볼륨을 체크한다.
n-1 파트에 나왔던 볼륨에서 현재 공연에서 조절할 수 있는 볼륨을 +, - 해준다.
여기서 중요한 점은 dp의 값을 바로 바꾸지 않는 것이다.
만약 dp[2] = 1에서 +2볼륨을 조절할 수 있어서 dp[4] = 1 -> 2로 바꿔주게 된다면, dp[4]에서 2번째 파트 음향이 나올 수 있는 가정을 판단해볼 수 없다.
현재 진행되는 공연 파트(n)에서 나올 수 있는 볼륨들(m)을 List에 저장하고, 한 번에 업데이트 해준다.
업데이트하면서 현재 공연 파트가 마지막 파트일 경우 볼륨의 최대값을 갱신해준다.

정답코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String NSM = br.readLine();
        StringTokenizer st = new StringTokenizer(NSM, " ");
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 각 곡마다 조절할 수 있는 볼륨 변화량
        String str = br.readLine();
        st = new StringTokenizer(str, " ");

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

        // 1. dp 테이블
        int[] dp = new int[M + 1]; // 특정 볼륨이 몇 번째 곡에서 가능한지를 저장
        Arrays.fill(dp, -1); // // 모든 볼륨을 초기에는 불가능 상태(-1)
        dp[S] = 0;  // 시작 볼륨 S는 0번째 곡에서 가능

        int ans = -1; // 최댓값 저장

        for (int n = 1; n <= N; n++) {
            List<Integer> change = new ArrayList<>(); // 현재 곡에서 가능한 볼륨 목록

            // 이전 곡(n-1)에서 나올 수 있는 볼륨
            for (int m = 0; m <= M; m++) {
                if (dp[m] == n - 1) { // 이전 곡에서 가능했던 볼륨이라면
                    int plus = m + arr[n];
                    int minus = m - arr[n];
                    
                    // 범위 이내라면 추가
                    if (plus <= M) change.add(plus);
                    if (minus >= 0) change.add(minus);
                }
            }

            for (int i = 0; i < change.size(); i++) {
                int change_idx = change.get(i);
                dp[change_idx] = n; // 현재 곡에서 이 볼륨이 가능한지 표시
                
                // 마지막 곡이라면 최댓값 갱신
                if (n == N) ans = Math.max(ans, change_idx);
            }
        }
        // 결과 출력
        System.out.println(ans);
    }
}