[백준BOJ] 1495번 기타리스트.java

 

백준 저지에서 기타리스트를 자바를 통해 풀어 보았다. 

 

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

1495번: 기타리스트

 

1495번 기타리스트.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1495번 기타리스트

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.
먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.
곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

설명

조합으로도 답은 나올 수 있으나 N이 최대 100까지 있기 때문에 시간 초과에 걸릴 가능성이 높다. 따라서 처음부터 DP로 접근하였다.

 

각 곡들은 순서대로 볼륨이 정해지면 모두 0부터 M 사이의 볼륨만 가질 수 있다. 곡은 1번부터 N번까지, 볼륨은 0부터 M까지므로 N+1행 M+1열 크기의 dp를 생성한다. 가질 수 있는 볼륨은 1, 없는 볼륨은 0으로 표시한다.

 

i+1번 째 곡이 가질 수 있는 볼륨은 i번 째 곡의 볼륨에서 v[i+1]을 더하거나 뺀 값이 0과 M사이일 때다. 따라서 재귀함수를 통해 1번 째 곡부터 1씩 증가시켜가면 가질 수 있는 볼륨의 크기가 j라면 dp[i][j]를 1로 초기화해준다.

 

단 가짓수에 따라 dp[i][j]에 중복되게 접근할 수 있다. dp[i][j]가 이미 1이라면 굳이 재방문할 필요가 없으므로 재귀함수를 종료한다.

코드

//1495번 기타리스트.java
package week7;

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

public class 기타리스트_1495 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int S;
    static int M;
    static int[]v;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
    	st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());//곡의개수
    	S = Integer.parseInt(st.nextToken());//시작볼륨
    	M = Integer.parseInt(st.nextToken());//볼륨은 M이하
    	
    	st = new StringTokenizer(br.readLine()," ");
    	v = new int[N+1];
    	for(int i=1;i<=N;i++)v[i]=Integer.parseInt(st.nextToken());
    	
    	dp = new int[N+1][M+1];
    	nextVolume(1,S);
    	
    	boolean check=true;
    	for(int i=M;i>=0;i--) {
    		if(dp[N][i]==1) {
    			System.out.println(i);
    			check=false;
    			break;
    		}
    	}
    	if(check)System.out.println(-1);
    	
	}
    public static void nextVolume(int i,int vol) {
    	if(i==N+1)return;
    	if(vol+v[i]<=M) {
    		if(dp[i][vol+v[i]]==0){
    			dp[i][vol+v[i]]=1;
        		nextVolume(i+1,vol+v[i]);
    		}
    		
    	}
    	if(vol-v[i]>=0) {
    		if(dp[i][vol-v[i]]==0){
    			dp[i][vol-v[i]]=1;
        		nextVolume(i+1,vol-v[i]);
    		}
    	}
    }
}