[BaekJoon] 1495 기타리스트 (Java)

🔗 문제 링크

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

📝 문제 풀이 방법

1. 최대 가장한 volume M을 표현할 수 있는 M+1크기의 배열을 만든다.
2. 현재 volume인 S를 True로 하여 초기값을 설정해준다.
3. M+1크기의 배열을 모두 탐색하며 input값에 따라 변경이 가능한 값들을 True로 변경해주며 반복문을 진행해주며 최종 결과를 얻는다.

👨🏻‍💻 작성한 코드

import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class B1495 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // Input 개수
		int S= Integer.parseInt(st.nextToken()); // 현재 볼륨
		int M = Integer.parseInt(st.nextToken()); // Max volume
		
		boolean[][] dp = new boolean[N+1][M+1];
		
		dp[0][S] = true;
		
		st = new StringTokenizer(br.readLine());
		
		for (int i=1; i<= N; i++) {
			int v = Integer.parseInt(st.nextToken());
			for (int j=0; j<=M; j++) {
				if (dp[i-1][j]) {
					if (j-v >= 0) dp[i][j-v] = true;
					if (j+v <= M) dp[i][j+v] = true;
				}
			}
		}
		
		int result = -1;
		for (int j=0; j<= M; j++) {
			if (dp[N][j]) result = j;
		}
		
		System.out.println(result);

	}
}