백준|1495번|기타리스트

문제설명
노래의 개수, 초기 볼륨, 최대 볼륨 그리고 각 노래가 시작할 때 변경할 수 있는 볼륨을 크기를 입력받고 공연을 할때마다 음악의 볼륨을 줄이거나 키운다고 할 때 마지막 곡을 연주할 수 있는 최대의 볼륨을 출력하는 문제입니다.(중간에 볼륨이 0이하로 가거나 최대 볼륨보다 커져서 마지막 곡을 연주할 수 없으면 -1을 출력합니다.)

작동 순서
1. 노래의 개수, 초기 볼륨, 최대 볼륨을 입력받습니다.
2. 각 노래가 시작할 때 변경할 수 있는 볼륨의 크기를 입력받습니다.
3. 각 노래를 시작할 때 마다 이전 노래에서의 볼륨들에서 변경이 가능한 경우들만 저장을 합니다.
4. 모든 공연을 한 뒤에는 마지막곡의 사용 가능 볼륨을 체크하며 가장 큰 값을 출력합니다. 만약 사용 가능 볼륨이 없으면 -1을 출력합니다.

소스코드

import java.io.*;
import java.util.StringTokenizer;

public class 백준_1495번_기타리스트 {
    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()), S = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
        int[][] list = new int[N+1][M+1];
        int[] v = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) v[i]=Integer.parseInt(st.nextToken());

        list[0][S]=1;
        for(int i=1;i<=N;i++){
            for(int j=0;j<=M;j++){
                if(list[i-1][j]==1){
                    if(j+v[i]<=M) list[i][j+v[i]]=1;
                    if(j-v[i]>=0) list[i][j-v[i]]=1;
                }
            }
        }
        for(int i=M;i>=0;i--){
            if(list[N][i]==1) {
                System.out.print(i);
                break;
            }
            if(i==0) System.out.print(-1);
        }
    }
}