BOJ 1495. 기타리스트

알고리즘 꾸준히 푸는거 뭔가 힘들닼ㅋㅋㅋㅋ
하루 1-2문제를 목표로 잡아서 그래도 괜찮을줄 알았는데 뭔가 꾸준히하기 힘들달까?
코딩테스트 기간에는 하루 5문제씩 풀었던거 같은데 어떻게 그랬는지 아직도 의문이다...ㅋㅋㅋㅋ
그리고 뭔가 요즘 자극이 부족한 느낌이랄까? 물론 요즘 갑작스런 일들이 많았어서 공부를 꾸준히 못하고 있는 이유도 있지만 뭔가 내 스스로 자극이 부족한 느낌도 있다... 어떻게 극복하지...
백준에서 문제 골라서 푸는거도 은근 힘들어서 여유 있는김에 LeetCode에서 스텝별로 풀어볼까 생각중....
옛날에 풀다 급해서 백준으로 양치기 했었는데... 흠... 이건 좀 더 고민해보구..

오늘은 기타리스트 문제를 풀었다.
오랜만에 푼 DP 문제였는데 DP치고는 쉬운 문제였다.
(DP는 작정하고 내면 진짜 생각도 못하겠음...)

내가 생각한 풀이법은 간단하다.
문제에서 주어진 범위가 작기도 하고, 모든 가능성에 대한 dp 배열을 생성해서 체크하는 방식으로 구현했다.
사실 이런 풀이는 모 아니면 도 느낌이 강한데 지금은 범위가 작기 때문에 시간 초과 없이 통과할 수 있지만 범위가 애매하거나 크다면 다른 풀이법을 생각해봐야할거 같다.

public class BOJ1495 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        int max = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] diff = new int[n];
        for(int index = 0; index < n; index++) {
            diff[index] = Integer.parseInt(st.nextToken());
        }

        boolean[][] dp = new boolean[n + 1][max + 1];
        dp[0][start] = true;
        for(int i = 0; i < n; i++) {
            boolean flag = true;
            for(int j = 0; j <= max; j++) {
                if(dp[i][j]) {
                    flag = false;

                    int small = j - diff[i];
                    int big = j + diff[i];

                    if(small >= 0) {
                        dp[i + 1][small] = true;
                    }
                    if(big <= max) {
                        dp[i + 1][big] = true;
                    }
                }
            }
            if(flag) {
                break;
            }
        }

        int answer = -1;
        for(int j = max; j >= 0; j--) {
            if (dp[n][j]) {
                answer = j;
                break;
            }
        }
        bw.write(answer + "");
        bw.flush();
        bw.close();
    }
}