Algorithm/DP

BOJ#1495 기타리스트

밤이2209 2017. 10. 9. 01:45

BOJ#1495 기타리스트


* 문제



* 풀이

dp[idx][volume] : N번째 곡일때, volume 가능 여부(boolean)




* 나의 코드

https://github.com/stack07142/BOJ/blob/b5664bd70b97831cf6d21fa7d0c37919da9508ce/BOJ%231495/src/Main.java


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

public class Main {

static int N, S, M;
static int[] V = new int[101];
static boolean[][] dp = new boolean[101][1001];

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken()); // 곡의 개수
S = Integer.parseInt(st.nextToken()); // 시작 볼륨
M = Integer.parseInt(st.nextToken()); // 최대 볼륨

st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {

V[i] = Integer.parseInt(st.nextToken());
}

// Solve
// dp[idx][volume] : N번째 곡일 때, Volume 가능 여부
dp[0][S] = true;

for (int idx = 1; idx <= N; idx++) {

for (int volume = 0; volume <= M; volume++) {

if (!dp[idx - 1][volume]) continue;

if (volume - V[idx] >= 0) dp[idx][volume - V[idx]] = true;

if (volume + V[idx] <= M) dp[idx][volume + V[idx]] = true;
}
}

for (int volume = M; volume >= 0; volume--) {

if (dp[N][volume]) {

System.out.println(volume);
return;
}
}

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


'Algorithm > DP' 카테고리의 다른 글

BOJ#1509 팰린드롬 분할  (0) 2017.10.27
BOJ#2352 반도체 설계  (0) 2017.10.09
BOJ#2631 줄세우기  (0) 2017.09.28
BOJ#2014 소수의 곱  (0) 2017.09.27
BOJ#10164 격자상의 경로  (0) 2017.09.26