Q1495. 기타리스트

볼륨을 저장하며 나아가는 로직

알고리즘이 필요 없네요.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1495 { static boolean[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int musicNum = Integer.parseInt(st.nextToken()); int startVolume = Integer.parseInt(st.nextToken()); int maxVolume = Integer.parseInt(st.nextToken()); dp = new boolean[101][1001]; st = new StringTokenizer(br.readLine()); dp[0][startVolume] = true; for (int i = 0; i < musicNum; i++) { int controlVolume = Integer.parseInt(st.nextToken()); for (int j = 0; j <= maxVolume; j++) { if (dp[i][j]) { int plusVolume = j + controlVolume; int minusVolume = j - controlVolume; if (plusVolume <= maxVolume) { dp[i+1][plusVolume] = true; } if (minusVolume >= 0) { dp[i+1][minusVolume] = true; } } } } int result = -1; for (int i = maxVolume; i >= 0; i--) { if (dp[musicNum][i]) { result = i; break; } } System.out.println(result); } }