[백준] 1495번: 기타리스트 (Java)

💡문제 분석 요약

N개의 각 곡을 연주하기 전에 볼륨을 V[i] 만큼 올리거나 내릴 수 있고, 볼륨은 0에서 M 사이여야 한다.

시작 볼륨 S에서 시작해서, 마지막 곡을 연주할 수 있는 최대 볼륨을 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• M+1 크기의 dp 배열을 생성한다. → dp[볼륨] = 연주 순서
• 볼륨 리스트가 {5, 3, 7}일 때:
  • 0번째 연주에서 가능한 볼륨은 S = 5 → dp[5] = 0
  • 1번째 연주에서 가능한 볼륨은 0, 10 → dp[0] = 1, dp[10] = 1
  • 2번째 연주에서 가능한 볼륨은 7, 3 → dp[7] = 2, dp[3] = 2
  • 3번째 연주에서 가능한 볼륨은 10, 0 → dp[10] = 3, dp[0] = 3
• N번째 곡의 볼륨 중 최댓값 → 값이 N인 dp의 인덱스 값 중 최대값

 

💡코드

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[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int S = Integer.parseInt(input[1]);
        int M = Integer.parseInt(input[2]);
        String[] volList = br.readLine().split(" ");

        int[] dp = new int[M+1];
        Arrays.fill(dp, -1);
        dp[S] = 0; // 0번째 연주에서 가능한 볼륨은 S
        for(int i=1; i<=N; i++) {
            int V = Integer.parseInt(volList[i-1]);
            List<Integer> possibleVol = new ArrayList<>();

            for(int j=0; j<=M; j++) {
                if(dp[j] == i-1) {
                    int case1 = j - V;
                    int case2 = j + V;
                    if(case1 >= 0 && case1 <= M) possibleVol.add(case1);
                    if(case2 >= 0 && case2 <= M) possibleVol.add(case2);
                }
            }

            for(int vol : possibleVol) {
                dp[vol] = i;
            }
        }

        int result = -1;
        for(int i=0; i<M+1; i++) {
            if(dp[i] == N) result = Math.max(result, i);
        }

        System.out.println(result);
    }
}

 

💡시간복잡도

$O(N*M)$

 

💡 틀린 이유

현재 단계에서 가능한 볼륨을 즉시 업데이트하도록 코드를 작성했다.

이렇게 하면 dp배열에 바로 업데이트하기 때문에, 같은 단계에서 이미 업데이트된 값이 다시 사용될 수 있다.

 

💡 틀린 부분 수정

가능한 볼륨을 리스트에 저장하고, 한 번에 업데이트 되도록 변경했다.

수정 전

for(int i=1; i<=N; i++) {
    int V = Integer.parseInt(volList[i-1]);
    for(int j=0; j<=M; j++) {
        if(dp[j] == i-1) {
            int case1 = j - V;
            int case2 = j + V;
            if(case1 >= 0 && case1 <= M) dp[case1] = i;
            if(case2 >= 0 && case2 <= M) dp[case2] = i;
        }
    }
}

 

수정 후

for(int i=1; i<=N; i++) {
    int V = Integer.parseInt(volList[i-1]);
    List<Integer> possibleVol = new ArrayList<>();

    for(int j=0; j<=M; j++) {
        if(dp[j] == i-1) {
            int case1 = j - V;
            int case2 = j + V;
            if(case1 >= 0 && case1 <= M) possibleVol.add(case1);
            if(case2 >= 0 && case2 <= M) possibleVol.add(case2);
        }
    }

    for(int vol : possibleVol) {
        dp[vol] = i;
    }
}

 

💡 느낀점 or 기억할정보

수정하기 전의 코드를 제출하고 틀렸다는 결과를 받고 나서, 한참동안 틀린 이유를 찾지 못했다. 결국 다른 풀이를 통해 틀린 이유를 알 수 있었다. 배열에 즉시 업데이트하면서 또 조건을 만족하는 값을 찾으면 당연히 잘못된 결과를 저장하게 될텐데 생각도 못했다ㅜ 이 문제도 꼭 다시 풀어봐야할 문제인 것 같다..