백준 1495 기타리스트(Java)

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

1495번: 기타리스트

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int s = sc.nextInt();
    int m = sc.nextInt();
    int[] arr = new int[n + 1];
    int[][] dp = new int[n + 1][m + 1];

    for(int i = 1; i <= n; i++) arr[i] = sc.nextInt();
    if(s + arr[1] <= m) dp[1][s + arr[1]] = 1;
    if(s - arr[1] >= 0) dp[1][s - arr[1]] = 1;

    for(int i = 2; i <= n; i++) {
      for(int j = 0; j <= m; j++) {
        if(dp[i - 1][j] == 1) {
          if(j + arr[i] <= m) dp[i][j + arr[i]] = 1;
          if(j - arr[i] >= 0) dp[i][j - arr[i]] = 1;
        }
      }
    }

    for(int i = m; i >= 0; i--) {
      if(dp[n][i] == 1) {
        System.out.println(i);
        return;
      }
    }

    System.out.println(-1);
  }
}