[백준] 1495 기타리스트 - 동적계획법(DP, Dynamic Programming) JAVA

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

1495번: 기타리스트

코드설명

DP 문제입니다.

 

이 문제에서 핵심은, DP[N+1][M+1] : N+1번쨰 노래에서 M+1 볼륨으로 노래를 킬 수 있는가입니다.

결국 마지막에는 DP[N][0 ~ M] 에서 가장 큰 볼륨인 M값을 출력하는것이 목표입니다.

 

DP[N+1][M+1] = boolean 으로 하지않아도되고,

DP[N+1] = M+1 로 하여서 기본값을 -1 으로 하여 진행할 수도 있습니다.

 

현재 노래가 N이라고 할때, N-1 중에서 노래를 모두 연주하지 못했다면 N번쨰 노래는 연주자체가 불가능합니다.

해당사항들을 고려하여 해결하면 됩니다.

 

재귀와 메모이제이션을 활용하여서도 작성했습니다.

문제에서 먼저 여러번 시행착오가 있었는데, 먼저, 91%에서 자꾸 틀리는 오류가 있었습니다.

 

해당 오류는 아래의 질문글을 보고 도움받았습니다.

https://www.acmicpc.net/board/view/138779

2 0 1
1 1

ans : 0

이 예제 코드를 돌려보면, answer ==0 일경우에는 단순히 0 을 출력하도록 처리하면 된다는 걸 알 수 있습니다.

저는 처음에 음악소리가 0일 경우는 없다고 생각하여 == 0 이면 -1 을 출력하도록 했습니다만, 0부터 M까지 모든 소리가 가능합니다.

 

해당 사유를 고치고나니 91%에서 이번엔 시간초과가 발생했습니다.

이미 메모이제이션을 적용시켜서 중복 연산이 발생하지 않는다고 생각했으나, 오산이었습니다.

시간초과 문제는, 아래의 변경점을 적용시켰습니다.

1. Cache 초기값을 -2 로 바꾼다. (cache[idx][nowVolume] != -2 라면 메모이제이션을 이용한다. 처음 Cache의 초기값은 -1 이었습니다. 즉 ret값과 같은 -1 입니다. )

2. ret 값은 -1 로 설정해서 만약 ret이 반환된다면 -1 불가능한것으로 인식하게한다. 이는 cache의 -2 와는 다른 의미를 가진 상태다.

for(int i=0;i<51; i++) {
    Arrays.fill(cache[i], -2);
}
static int DFS(int idx, int nowVolume) {
    if(idx == N) return nowVolume;
    if(cache[idx][nowVolume] != -2) return cache[idx][nowVolume];

    int ret = -1;
    if(nowVolume + arr[idx] <= M) {
        ret = Math.max(ret, DFS(idx + 1, nowVolume + arr[idx]));
    }
    if(nowVolume - arr[idx] >= 0) {
        ret = Math.max(ret, DFS(idx + 1, nowVolume - arr[idx]));
    }

    return cache[idx][nowVolume] = ret;
}

 

위의 코드처럼 수정해야 합니다.

 

가장 중요한곳은 아래입니다.

for(int i=0;i<51; i++) {
    Arrays.fill(cache[i], -2);
}

cache[i] = -2로 모두 설정해서, cache[i] = -2 일떄의 의미를 아직 한번도 해당 공간에 접근하지 못했다는 상태를 의미하도록 합니다.

만약 cache[i] != -2 가 아니라면 해당 구간이 실패한더라도 어쨋든간에 방문은 한것이기에 중복재귀방문 하지않도록 하여 시간초과를 피할 수 있습니다.

문제점은, -1은 cache에서도 쓰이고 ret에서도 함께 쓰이는 상태인것이 문제였습니다. -1 은 해당 음악을 틀 수 있는 방법이 없다는 상태를 의미하고 있습니다. (즉, 실패하더라도 해당 공간으로 가면 실패한다는 것을 이미 알면 다시는 못가게 처리해야한다는 것이지요.)

아마, 문제자가 일부러 이렇게 아무런 의식없이 cache값을 -1 로 설정시키도록 하는 개발자들을 대상으로 의식적으로 생각하도록 문제를 출제한 것 같습니다. 좋은 문제입니다.

코드

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

public class Main {
	
	public static int N, S, M;
	public static boolean[][] dp;
	public static int[] volume;
	public static int answer = 0;
	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());
    	
    	dp = new boolean[N+1][M+1]; //N+1 번째 연주곡이 M+1의 볼륨을 연주가능한지 아닌지 여부를 Return 합니다.
    	
    	dp[0][S] = true;  //0번째 곡은 S 볼륨으로 연주할 수 있다.
    	
    	volume = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=1; i<=N; i++) {
    		volume[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=1; i<=N;i++) {
    		for(int j=0; j<=M ;j++) {
    			if( !dp[i-1][j]) continue; //이걸 위해 dp[0][S] = true로 설정합니다.
    			if( j + volume[i] <= M) {
    				dp[i][j + volume[i]] = true;
    			}
    			if( j - volume[i] >= 0) {
    				dp[i][j - volume[i]] = true;
    			}
    		}
    	}
    	
    	for(int j=M; j>=0; j--) {
    		if(dp[N][j] == true) {
    			System.out.println(j);
    			return ;
    		}
    	}
    	System.out.println(-1);
    	
    }
}

 

재귀 + 메모이제이션을 활용합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int[] arr = new int[51];
	static int[][] cache = new int[51][1001];
	static int answer = 0;
	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=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<51; i++) {
			Arrays.fill(cache[i], -2);
		}
		answer = DFS(0, S);
		System.out.println(answer);
	}
	
	static int DFS(int idx, int nowVolume) {
		if(idx == N) return nowVolume;
		if(cache[idx][nowVolume] != -2) return cache[idx][nowVolume];
		
		int ret = -1;
		if(nowVolume + arr[idx] <= M) {
			ret = Math.max(ret, DFS(idx + 1, nowVolume + arr[idx]));
		}
		if(nowVolume - arr[idx] >= 0) {
			ret = Math.max(ret, DFS(idx + 1, nowVolume - arr[idx]));
		}
		
		return cache[idx][nowVolume] = ret;
	}
	
}