백준 1495 기타리스트 (Java)

1. 문제 링크

1495번: 기타리스트

 

2. 문제 및 입출력예제

 

3. 문제 풀이

vol 배열에 시작 볼륨부터 입력받은 변경 값들을 저장한다.

visit 배열을 이용해서 곡 순서와 볼륨에 true를 넣어서 중복되지 않게 한다.

0과 최댓값 사이에 있지 않은 곡 순서와 볼륨일 경우 visit 배열에 -1을 넣고 return한다.

3에서 걸리지 않으면 다음 곡으로 넘어가서 재귀를 한다.

곡의 순서가 마지막까지 오면 그때의 볼륨과 최댓값을 비교해 최댓값을 정했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;

public class Main {
	private static int n, s, m, max;
	private static int vol[], visit[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
		String[] nsm = br.readLine().split(" ");
		n = Integer.parseInt(nsm[0]);
		s = Integer.parseInt(nsm[1]);
		m = Integer.parseInt(nsm[2]);
		vol = new int[n+1];
		max = -1;
		String[] split = br.readLine().split(" ");

		vol[0] = s;
		for (int i = 1; i < n+1; i++) {
			vol[i] = Integer.parseInt(split[i-1]);
		}

		visit = new int[n+2][m+1];
		recursion(1,s);

		System.out.println(max);
	}

	private static void recursion(int start, int sum) {
		if(start == n+1) {
			max = Math.max(max, sum);
			return;
		}
		visit[start][sum] = 1;
		int plus = sum + vol[start];
		int minus = sum - vol[start];
		if(plus > m && minus < 0) {
			visit[start][sum] = -1;
			return;
		}
		if(plus<=m && visit[start+1][plus]!=1) { 
			recursion(start+1, plus);
		}
		if(minus>=0 && visit[start+1][minus]!=1) {
			recursion(start+1, minus);
		}
		return;
	}	
}