[baekjoon] 1495. 기타리스트 - dp 값 범위 보고 유추해보기

https://www.acmicpc.net/problem/1495

 

문제의 범위가 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M)  였기 때문에 

boolean[][] dp = new boolean[N + 1][M + 1]; 만큼 돌려도 충분히 시간에 들어온다.

 

이부분을 미리 캐치했다면 좀 더 유추하기 쉬웠지 않을까 싶다.

 

앞에 가능한 수를 미리 찾고 뒤에도 계속 찾기...

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
  static int N, S, M;
  static int[] arr;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    pro();
  }

  static void pro() {
    boolean[][] dp = new boolean[N + 1][M + 1];
    dp[0][S] = true;
    for (int i = 1; i <= N; i++) {
      boolean check = false;

      for (int j = 0; j <= M; j++) {
        if (!dp[i - 1][j]) continue;
        for(int k : new int[] {j - arr[i], j + arr[i]}) {
          if(k < 0 || k > M) continue;
          dp[i][k] = true;
          check = true;
        }
      }
      if(!check) {
        System.out.println(-1);
        break;
      }
    }
    for(int i=M ; i>=0 ; i--){
      if(!dp[N][i]) continue;
      System.out.println(i);
      break;
    }
  }

  static void input(BufferedReader br) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    S = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    arr = new int[N+1];
    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
  }
}