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

BOJ Link

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

 

풀이 과정

0이상 M이하의 범위를 지키면서,

처음 값 S에서 V[0]...V[N-1]을 가감하며 탐색할 수 있는 지 찾는 문제이다. 할 수 있는 경우가 여러개라면 최대값을 출력한다.

 

현재 dp[i][j]를 P비용으로 연주하려면, dp[i-1][j-P]나 dp[i-1][j+p]가 true면 된다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    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());
        int S = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] V = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        boolean[][] dp = new boolean[N][M + 1];

        if (S + V[0] <= M)
            dp[0][S + V[0]] = true;
        if (S - V[0] >= 0)
            dp[0][S - V[0]] = true;

        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= M; j++) {
                if (j - V[i] >= 0 && dp[i - 1][j - V[i]])
                    dp[i][j] = true;
                if (j + V[i] <= M && dp[i - 1][j + V[i]])
                    dp[i][j] = true;
            }
        }

        int ans = -1;
        for (int i = 0; i <= M; i++) {
            if (dp[N - 1][i]) ans = i;
        }

        System.out.println(ans);
    }
}