Baekjoon 1495 기타리스트 JAVA

1495번: 기타리스트

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

풀이

시작하는 볼륨 S로부터 입력받는 볼륨을 계산한다.

처음으로 나올 수 있는 음악 볼륨으로 초기화 해준다.

초기화가 되지 않는다면 다음의 값은 이미 -1로 되있기에 값의 변화가 없을 것이다.

 

곡은 끊임없이 마지막까지 연주되어야 하기에 일차원 배열 하나를 중복적으로 이용하지 않고,

이차원 배열을 생성하여 각각의 곡에 대한 연주 가능 여부를 판단한다.

 

노래가 넘어갈때 마다 이전에 있던 값이 0이상일 경우는 값이 초기화 된 이후로 연주할 수 있는 노래이며

동시에 주어진 M값보다 작다는 것을 의미하기에, 연주할 수 있는 노래이다.

 

모든 곡을 연주했다면 마지막에 들어갈 수 있는 값을 검사하면서 들어있는 값을 이용하여 연수 할 수 있는 최대 볼륨을 구한다.

 

 코드 참고

코드

import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(), s=sc.nextInt(), m=sc.nextInt();
		int [] v = new int [n];	// 입력받는 볼륨
		int [][] dp=new int[n][m+1];	// 행은 n번째 볼륨, 열은 낼 수 있는 볼륨
		for(int i=0;i<n;i++) {
			v[i]=sc.nextInt();
			Arrays.fill(dp[i], -1);	// 전체를 -1로 초기화
		}
		int r1=s+v[0], r2 = s-v[0];	// 1번째 음악을 틀기 전에 볼륨 조절을 하기에 처음에 초기화
		if(r1>=0 && r1<=m)
			dp[0][r1]=r1;	// MAX값을 출력할 때 최대 값을 출력하기에 저장되는 값을 볼륨의 값으로 저장 
		if(r2>=0 && r2<=m)
			dp[0][r2]=r2;

		for(int i=1;i<n;i++) {	// 두번째 볼륨부터 확인
			for(int j=0;j<=m;j++) {	// 0부터 최대 볼륨까지 검사하면서 
				if(dp[i-1][j]>=0) {	// 앞선 볼륨 중 하나라도 도달 가능하면 그 볼륨부터의 탐색 
					r1=j+v[i];
					r2=j-v[i];
					if(r1>=0 && r1<=m)
						dp[i][r1]=r1;
					if(r2>=0 && r2<=m)
						dp[i][r2]=r2;
				}
			}
		}
		
		int ans=-1;	// 아무것도 출력이 안된다면 -1이기에 -1부터 비교
		for(int j=0;j<=m;j++) {
			ans=Math.max(ans, dp[n-1][j]);	// 최대 볼륨 크기까지 검사하면서 저장된 값 중 가장 큰 볼륨을 출력
		}
		System.out.println(ans);
	}
}