백준 1495. 기타리스트

🅰 백준 1495. 기타리스트

1495번: 기타리스트

✏️ 문제 풀이

• 기타리스트 문제에서는 행을 각 곡의 개수, 열을 0~M(최대 볼륨)으로 설정한 다음 dp를 수행한다
• 점화식은 D[i][j] = D[i+1][j+V[i+1]] = 1, D[i+1][j-V[i+1]] = 1이 될 수 있다.
• i+1에 데이터를 저장할 때 0~M사이에 있으면 dp에 저장을 하면서 마지막 곡까지 반복수행한다.
• 마지막 곡의 볼륨조절이 끝난 후 그 행에 있는 볼륨 중 최대값을 출력하면 최대값을 출력한다.

✏️ 소스코드

package dp;

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;
/*
 * 점화식 : D[i][j]가 1이면 D[i+1][j+V[i+1]]도 1, D[i+1][j-V[i+1]]도 1이 될 수 있다.*/
public class Main_실버1_1495_기타리스트 {

	public static void main(String[] args) throws Exception {
		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 D[][] = new boolean[101][1001];
		int ans = -1;
		int vol[] = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			vol[i] = Integer.parseInt(st.nextToken());
		}
		
		// 기저조건
		if(S-vol[0]>=0) D[0][S-vol[0]] = true;
		if(S+vol[0]<=M) D[0][S+vol[0]] = true;

		for (int i = 0; i < N-1; i++) {
			for (int j = 0; j <= M; j++) {
				if(!D[i][j]) continue;
				
				if(j-vol[i+1] >= 0) {
					D[i+1][j-vol[i+1]] = true;
				}
				if(j+vol[i+1]<=M) {
					D[i+1][j+vol[i+1]] = true;					
				}
			}
		}
		for (int i = 0; i <= M; i++) {
			if(D[N-1][i] && i>ans) ans = i;
		}
		System.out.println(ans);
	}
}

 

✅ 후기

• dp는 2차원배열로 푼다면 행과 열을 어떤 걸로 정할지가 가장 중요한 것 같다.(개인적인 생각) 물론 3차원 배열 등 다양한 방법들을 이용해서 푸는 법을 더 익혀야겠다.