[PS] BOJ1495 기타리스트 ( dp ) with JAVA

 

1495번: 기타리스트

 

 

◎ 문제풀이

 

개인적으로 이렇게 넓은 범위의 경우의 수를 갖는 DP 문제를 푼 것이 처음이기에 풀이를 잘 이어가지 못했다. 

 

 

 

 

 

볼륨은 매 곡마다 정해진 크기만큼 올리거나 내릴수 있다. 시작볼륨이 5라고 했을때, 곡이 진행되면 진행될수록 그 경우의 수는 2배씩 증가한다. 볼륨의 최대 크기도 정해져 있으니 무조건 매 곡 볼륨을 증가한다고 최대 볼륨이 되는 것 또한 아니다. 모든 경우의 수가 최대 볼륨이 될 수 있는 가능성이 있는 것이다. 그러므로 모든 경우의 수를 고려해야 한다. 볼륨을 최대로 바꿀 수 있는 한계는 1000이다. 0 과 1000 사이의 볼륨 중 현재 곡에서 최대 볼륨이 되는 경우의 수를 구해야 한다.  

 

 

◎ 코드 

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

import static java.lang.Math.*;

//BOJ1495 기타리스트
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];
        boolean[][] dp = new boolean[n+1][m+1]; // DP 테이블

        dp[0][s] = true; // 시작 볼륨 

        // 매곡 볼륨 초기화
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<n+1;i++){
            volumes[i] = Integer.parseInt(st.nextToken());
        }

        // DP 시작
        for(int i=1;i<n+1;i++){
            int volume = volumes[i];
            for(int j=0;j<=m;j++){ // 0 - 최대 1000 볼륨 사이에 변경 가능한 경우에 true 초기화하기
                if(dp[i-1][j]){
                    if(j+volume <= m) dp[i][j+volume] = true;
                    if(j-volume >= 0) dp[i][j-volume] = true;
                }
            }
        }

        // n번째 곡에서 변경 가능한 볼륨 중 최대값 출력하기  
        int ans = -1;
        for(int i=m;i>-1;i--){
            if(dp[n][i]){
                ans = i;
                break;
            }
        }

        System.out.println(ans);
    }
}