기타리스트(1495번)

• 티어 : Sliver 1
• 정답여부 : 오답
• 알고리즘 유형 : 다이다믹 프로그래밍
• 시간 제한 : 2초

💡문제

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을 출력한다.

💡예제 입력 1

3 5 10
5 3 7

💡예제 출력 1

10

💡예제 입력 2

4 8 20
15 2 9 10

💡예제 출력 2

-1

💡예제 입력 3

14 40 243
74 39 127 95 63 140 99 96 154 18 137 162 14 88

💡예제 출력 3

238

💡문제요약

• 마지막 곡의 최대 볼륨을 구하면 되는 문제

💡알고리즘 설계

• N : 곡의 개수
• S : 시작 볼륨
• M : 최대 볼륨
• volumes : 각 곡의 볼륨들의 값

1. dp[곡 수][볼륨의 최대수+1]로 설정

2. 2차원배열에 초기볼륨으로부터 +, - 한값들을 배열에 1을 각각 저장

   → 첫번째 곡은 0과 10 이니 [0.0][0,10] 각 배열에 1을 저장해줌

3. 마지막 곡을 연주할 때 가능한 볼륨 중 가장 큰 값을 찾아 출력

💡작성코드

• Java

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));
		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[] volumes = new int[N+1];
		int max = -1;
		st = new StringTokenizer(br.readLine()); 
        for (int i = 1; i <= N; i++) {
            volumes[i] = Integer.parseInt(st.nextToken()); // 각 곡을 연주할 때 조절할 수 있는 볼륨의 변화량
        }
		int [][] dp = new int[N + 1][M + 1]; // 볼륨
		dp[0][S] = 1;
		for(int i = 1; i < N+1; i++) {
			for(int j = 0; j < M + 1; j++) {
				if(dp[i-1][j] == 1) {
					if(j + volumes[i] <= M) {
						dp[i][j+volumes[i]]=1;
					}
					if(j-volumes[i]>=0){
                        dp[i][j-volumes[i]]=1;
                    }
				}
			}
		}
		for(int i=0; i<M+1;i++){
            if(dp[N][i]==1){
                max = Math.max(max, i);
            }
        }
        System.out.println(max);	
	}
}

💡시간복잡도

O(N)

💡틀린 이유 or 수정할 부분

진짜 처음에 문제 풀때 너무 어려웠다. 문제 이해가 안되서 1시간 끙끙 거리다가 도저히 이해가 안 가서 구글링을 통해 다른 사람 문제 설명을 보고 이해를 하며 한번 스스로 코드를 구현했다. 뭔가 어렵다고 생각하니까 더 문제가 이해가 안 가는거 가다.

다른 사람들 코드를 보면서 top - down 으로 구현하신분들도 있어서 가져와봤다.

💡틀린 부분 수정 or 다른풀이

• Java

package algorithms_Java04_02;
import java.io.*;
import java.util.*;
public class baekjoon_1495 {
    static int N, S, M;
    static int[] volumes;
    static Integer[][] dp; // Integer로 변경하여 null값을 체크할 수 있게 함
    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());
        volumes = new int[N+1];
        dp = new Integer[N+1][M+1]; // 메모이제이션을 위한 dp 배열
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            volumes[i] = Integer.parseInt(st.nextToken());
        }
        int result = solve(N, S);
        System.out.println(result >= 0 ? result : -1);
    }
    static int solve(int song, int volume) {
        // 볼륨 범위를 벗어나는 경우
        if (volume < 0 || volume > M) return -2;
        // 모든 곡을 다 처리한 경우
        if (song == 0) return volume;        
        // 이미 계산된 경우
        if (dp[song][volume] != null) return dp[song][volume];
        // 두 가지 경우를 모두 고려하여 최댓값을 찾음
        return dp[song][volume] = Math.max(solve(song - 1, volume + volumes[song]),
                                            solve(song - 1, volume - volumes[song]));
    }
}

💡느낀점 or 기억할 정보

dp 진짜 어렵다. 일단 문제에 개념 이해가 안 가니까 코드를 구현할 엄두가 안 난다. 그리고 정말 많이 풀어야봐야겠다는 생각이 들었다. ..