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

1. 문제유형 : DP

2. 시간복잡도 : O(2^N)

 

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

public class Main {
	
	public static int N, S, M, V[], answer = -1;
	public static boolean cache[][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		cache = new boolean[N+1][M+1];
		V = new int[N+1];
		st = new StringTokenizer(in.readLine());
		for (int i = 1; i <= N; i++) {
			V[i] = Integer.parseInt(st.nextToken());
		}
		
		solve(0, S);
		System.out.println(answer);
		
	}
	
	public static void solve(int idx, int v) {
		if(idx == N) {
			answer = Math.max(answer, v);
			return;
		}
		
		if(cache[idx][v]) return;
		
		cache[idx][v] = true;
		if(v + V[idx+1] <= M) solve(idx+1, v + V[idx+1]);
		if(v - V[idx+1] >= 0) solve(idx+1, v - V[idx+1]);
	}

}