[백준 1495] 기타리스트 - JAVA // le_effort//

사용 알고리즘 : DP

 

dp배열 설정 (boolean)

dp[i][j]

[i번째 곡으로][볼륨 j를 연주 할 수 있는지]

 

주의 할 점 : 볼륨 0도 연주를 할 수 있다고 친다.

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,s,m;
    static boolean dp[][];
    static int vol[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);     // 곡 개수
        s = Integer.parseInt(t[1]);        // 시작볼륨
        m = Integer.parseInt(t[2]);    // 최대볼륨
        vol = new int[n+1];
        
        String[] tt = br.readLine().split(" ");
        for(int i=1; i<=n; i++) {
            vol[i] = Integer.parseInt(tt[i-1]);
        }
        dp = new boolean[n+1][m+1];
        
        dp[0][s]=true;
        
        for(int i=1; i<=n; i++) {
            for(int j=0; j<=m; j++) {
                if(!dp[i-1][j]) {
                    continue;
                }    // 전단계가 성립이 안되면 계속 할 이유가 없다.
                if(j+vol[i]<=m) {
                    dp[i][j+vol[i]]=true;
                }
                if(j-vol[i]>=0) {
                    dp[i][j-vol[i]] = true;
                }
            }
        }
        
        for(int i=m; i>=0; i--) {
            if(dp[n][i]) {
                System.out.println(i);
                System.exit(0);
            }
        }
        System.out.println(-1);
    }
}