백준 1495(기타리스트) - Python(파이썬),Java(자바) - 다이나믹 프로그래밍

1495번: 기타리스트

예제 풀이

1) 시작 볼륨(S)= 5일 바꿀 수 있는 볼륨  -> 0 , 10 

=> 5-v[0] = 0 or 5+v[0] = 10

0	1	2	3	4	5	6	7	8	9	10
1										1

2) 현재 볼륨이 0과 10인 경우 바꿀 수 있는 볼륨 -> 3 , 7

=> 0-v[1] = -3(0보다 작으므로 X) or 0+v[1] = 3 or 10-v[1] = 7 or 10+v[1] = 13(최댓값 10보다 크므로 X)

0	1	2	3	4	5	6	7	8	9	10
			1				1

3) 현재 볼륨이 3과 7인 경우 바꿀 수 있는 볼륨 -> 0, 10

=> 3-v[2] = -4(0보다 작으므로 X) or 3+v[2] = 10 or 7-v[2] = 0 or 7+v[2] = 14(최댓값 10보다 크므로 X) 

0	1	2	3	4	5	6	7	8	9	10
1										1

 

최종적으로 가장 큰 값이 10이 나온다.

<dp 테이블>

0	1	2	3	4	5	6	7	8	9	10
1										1
			1				1
1										1

---

1) 시작 볼륨(S)= 8일 바꿀 수 있는 볼륨  -> 없음

=> 8-v[0] = -7(0보다 작으므로 X)  or 8+v[0] = 23(20보다 크므로 X)

2) 마지막 곡을 연주할 수 없으므로 -1을 출력

 

문제 풀이

① dp 테이블 생성 ( 행 : (인덱스가 0부터 n까지) n+1개  | 열 : (0부터 m까지) m+1개 )
  -> 처음 시작 0번째 부터 곡의 개수 (n)까지 하므로 n+1개 , 볼륨은 0부터 m까지 이므로 m+1개 
② dp[i][index] 테이블에 값이 1인 경우
  -> index + v[i] <=m : dp의 다음 행인 i+1번의 행에 index +v[i] 열의 값을 1로 변경
  -> index - v[i] >=0 : dp의 다음 행인 i+1번의 행에 index-v[i] 열의 값을 1로 변경
③ ②을 i=0부터 n-1까지 실행하여 dp 테이블 변경
④ 마지막 행인 n에서는 1이 없는 경우 -1을 출력 , 1이 있을 경우에는 가장 최댓값을 출력

💻Python(파이썬)

import sys
n,s,m = map(int,sys.stdin.readline().split())
#dp 테이블 생성
dp = [[0]*(m+1) for _ in range(n+1)]
#i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 크기
v = list(map(int,sys.stdin.readline().split()))
#처음 시작 볼륨의 값 지정
dp[0][s]=1

for i in range(n):
    #dp[i]테이블의 인덱스 (index) , dp[i] 테이블의 번호(num)
    for index,num in enumerate(dp[i]):
        #현재 볼륨
        if num==1:
            #다음 볼륨이 0부터 m 사이의 경우 -> 바꿀수 잇는 볼륨
            if index+v[i]<=m:
                dp[i+1][index+v[i]]=1
            if 0<=index-v[i]:
                dp[i+1][index-v[i]]=1

#마지막 행에 1이 없는 경우 -> 연주할 수 있는 볼륨이 없음
if 1 not in dp[n]:
    print(-1)
#마지막 행에 1이 있는 경우 
else:
    print(max([i for i,num in enumerate(dp[n]) if num==1 ]))

💻Java(자바)

import java.io.*;
import java.util.*;

public 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[][] dp = new int[N+1][M+1];
        st = new StringTokenizer(br.readLine()," ");
        dp[0][S]=1;
        for(int i=0;i<N;i++){
            int a = Integer.parseInt(st.nextToken());
            for(int j=0;j<M+1;j++){
                if(dp[i][j]==1){
                    if(j+a<=M){
                        dp[i+1][j+a]=1;
                    }
                    if(j-a>=0){
                        dp[i+1][j-a]=1;
                    }
                }
            }
        }
        int result =-1;
        for(int i = M;i>=0;i--){
            if(dp[N][i]==1){
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}