[BaekJoon] 1495 기타리스트

1.  문제 링크

2.  문제

요약

• N개의 곡을 연주하는데 각각의 곡이 시작하기 전에 i번째 곡에 대해서 V[i]만큼의 볼륨을 조정할 수 있습니다.
• 즉, 현재 볼륨이 P이고 i번째 곡을 연주하기 전이라면 i번째 곡은 P + V[i] 또는 P - V[i]의 볼륨으로 연주합니다.
• 이 때, 볼륨은 0보다는 크거나 같고 M보다는 작거나 같아야 합니다.
• 연주할 곡의 개수 N, N개의 곡에 대한 볼륨의 리스트 V, 시작 볼륨 S, 최대 볼륨 M이 주어졌을 때 마지막 곡의 볼륨 중 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 N, S, M이 주어지고 두 번째 줄에 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이 V가 주어집니다.
• 출력: 첫 번째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력합니다.

3.  소스코드

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

public class Main {
	int[][] dp;
	static int start_vol, max_vol, song_num;
	static int[] dif_volume;
	
	public int findVolume(int sum, int index) {
		if(0 > sum || sum > max_vol) {
			return -1;
		}
		if(index == song_num) {
			return sum;
		}
		if(dp[sum][index] != -10) {
			return dp[sum][index];
		}
		return dp[sum][index] = Math.max(dp[sum][index], Math.max(findVolume(sum + dif_volume[index], index + 1), findVolume(sum - dif_volume[index], index + 1)));
	}
	
	public int getMaxVolume() {
		dp = new int[max_vol + 1][dif_volume.length];
		for(int i = 0; i < dp.length; i++) {
			for(int j = 0; j < dp[i].length; j++) {
				dp[i][j] = -10;
			}
		}
		return findVolume(start_vol, 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		song_num = Integer.parseInt(st.nextToken());
		start_vol = Integer.parseInt(st.nextToken());
		max_vol = Integer.parseInt(st.nextToken());
		dif_volume = new int[song_num];
		input = br.readLine();
		br.close();
		st = new StringTokenizer(input);
		for(int i = 0; i < dif_volume.length; i++) {
			dif_volume[i] = Integer.parseInt(st.nextToken());
		}
		Main m = new Main();
		bw.write(m.getMaxVolume() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 DP를 이용하여 해결할 수 있습니다.

1. dp라는 2차원 배열을 만들고 아직 방문되지 않은 곳을 -10이라는 값으로 표현하기 위해 dp 배열을 -10이라는 값으로 초기화시킵니다.
2. 시작 볼륨부터 시작하여 다음 볼륨으로 (현재 볼륨 - 다음 곡 볼륨)과 (현재 볼륨 + 다음 곡 볼륨)이 가능한데 마지막 곡의 볼륨을 최대로 해야 하므로 둘 중 더 큰 값을 취하고 그 값과 현재 볼륨 중 더 큰 값을 현재 볼륨으로 취하게 됩니다.
3. 이 때, 볼륨이 0보다 작거나 M보다 크면 안되므로 문제에서 마지막 곡을 연주할 수 없다면 -1을 출력하라고 하였기 때문에 해당 경우에는 -1이라는 값을 취합니다.
4. 또한 index가 전체 개수를 모두 돌았다면 마지막 곡의 볼륨이 sum이 되기 때문에 이 때 sum을 반환합니다.
5. 2번 과정에서 (현재 볼륨 - 다음 곡 볼륨)과 (현재 볼륨 + 다음 곡 볼륨) 부분은 재귀를 이용하여 마지막까지 돌 수 있도록 해주고 이 과정을 통해 마지막 곡에서 가능한 최대 볼륨을 구할 수 있습니다.