[Silver I] 기타리스트 - 1495

문제 링크

성능 요약

메모리: 14248 KB, 시간: 124 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 7월 20일 02:59:00

문제 설명

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

풀이 (DP)

위 문제는 이차원 DP 배열을 사용해 해결할 수 있었다.
[1차원 DP 풀이] : 1차원 풀이를 보고 싶거나, 다른 해결 방식을 보고 싶은 경우, 위 블로그 내용이 충분히 도움이 될 것 같다.

DP 이차원 배열을 DP[곡 개수][볼륨] 형태로 사용했다.
각각의 곡 순서에 따라 P + V[i] / P - V[i] 가 범위에 부합한다면 true를 할당하는 방식으로 2중 for문을 사용해 만약 전 단계에서 true인 경우엔 P + V[i] / P - V[i] 를 계산해 계속 이어나가는 방식이다.

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

public class Main {
	//DP 문제
	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());
		
		boolean[][] dp = new boolean[N+1][M+1]; //DP배열 [곡의 개수][최대 볼륨]
		int[] V = new int[N+1]; //볼륨 배열
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			V[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0][S]=true; //초기 시작 TRUE
        
		for(int i=1; i<=N; i++) {
			for(int j=0; j<=M; j++) {
				if(dp[i-1][j]) {
					int max_value = j + V[i]; // +일 때
					int min_value = j - V[i]; // -일 때
					if(min_value>=0) {
						dp[i][min_value]=true;
					}
					if(max_value<=M) {
						dp[i][max_value]=true;
					}
				}
			}
		}
        
		int ans=-1;
		for(int i=M; i>=0; i--) {
			if(dp[N][i]) {
				ans=i;
				break;
			}
		}
		System.out.println(ans);
	}
}

dp를 이차원 배열로 쓰는 것이 익숙하지 않기도 하고 위 문제같이 dp를 정수 배열이 아닌 boolean 형태로 체크해나가는 방식은 접해보지 못해 더욱 어려웠던 문제다.
dp도 다시 꾸준히 공부하며 좀 더 익힐 필요가 있음을 느꼈다...