[백준] 1495번 '기타리스트' - Java

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

---

문제

---

풀이

이 문제의 핵심 조건은

1. 연주 순서대로 입력되는 곡

2. 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 있음

이었습니다.

 

DP를 이용하여 풀이했습니다.

v배열에는 시작하기 전에 곡에 줄 수 있는 볼륨의 차이를 담고, dp배열의 인덱스의 의미는볼륨, 즉 m까지 담을 수 있으며 각 밸류의 의미는 곡의 순서를 의미합니다. 즉, v배열의 인덱스를 의미합니다.

 

for(int v_idx=1; v_idx<=n; v_idx++) {
			Queue<Integer> q = new LinkedList<>();
			for(int dp_idx=0; dp_idx<=m; dp_idx++) {
				if(v_idx-1 == dp[dp_idx]) {
					int positive = dp_idx + v[v_idx];
					int negative = dp_idx - v[v_idx];
					
					if(positive <= m) q.add(positive);
					if(negative >= 0) q.add(negative);
				}
			}
			while(!q.isEmpty()) {
				int idx = q.poll();
				dp[idx] = v_idx;
			}
		}

 

크게 v 값을 전체적으로 돌면서, dp와 비교하며 돌아갑니다.

처음 상태를 나타내야 하기에 처음 모든 인덱스 값이 -1로 초기화 되어있던 dp는 s 인덱스에서 0이 됩니다. 순서가 0번째라는 의미입니다. (그런 이유로 v 인덱스를 1부터 시작합니다)

dp[s] = 0;

 

v 인덱스의 이전 값, 즉 이전 순서에 갱신을 해야하므로 v_idx - 1과 같은지 비교합니다.

그 다음으로는 이전 값에서 ±v[v_idx] 햇을 때에 0이상 M 미만 범위에 들어오는지 확인 후, 갱신합니다.

갱신할 때에 주의할 점은, dp_idx를 돌리는 for문 안에서 갱신을 할 경우, positive, negative 중 하나가 갱신 되지 못 할 경우가 있습니다.

2 1 4
1 2

 

의 경우라고 했을 때, 그의 경우가 그렇습니다. (답은 4)

참고:  https://www.acmicpc.net/board/view/94032

그래서 이용한 것이 Queue를 이용하여 저장해두었다가, 한꺼번에 갱신시키는 것입니다.

 

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

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 = 0, s = 0, m = 0;
		n = Integer.valueOf(st.nextToken());
		s = Integer.valueOf(st.nextToken());
		m = Integer.valueOf(st.nextToken());
		
		int[] v = new int[n+1];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1; i<=n; i++) {
			v[i] = Integer.valueOf(st.nextToken());
		}
		int[] dp = new int[m+1];
		for(int i=0; i<=m; i++) dp[i] = -1;
		
		solution(n, s, m, v, dp);
		
		for(int i=m; i>=0; i--) {
			if(dp[i] == n) {
				System.out.println(i);
				return;
			}
		}
		System.out.println(-1);
	}
	
	public static void solution(int n, int s, int m, int[] v, int[] dp) {
		dp[s] = 0;
		
		
		for(int v_idx=1; v_idx<=n; v_idx++) {
			Queue<Integer> q = new LinkedList<>();
			for(int dp_idx=0; dp_idx<=m; dp_idx++) {
				if(v_idx-1 == dp[dp_idx]) {
					int positive = dp_idx + v[v_idx];
					int negative = dp_idx - v[v_idx];
					
					if(positive <= m) q.add(positive);
					if(negative >= 0) q.add(negative);
				}
			}
			while(!q.isEmpty()) {
				int idx = q.poll();
				dp[idx] = v_idx;
			}
		}
	}
}

 

---

후기

위의 반례에서 굉장한 삽질을 하다가 끝끝내 답을 찾았습니다..

처음에는 -1도 안 써서 틀렸더랬죠

반례를 찾는 건 어떻게 찾는걸까요? 무지성 반례 찾기 -> 복붙 -> 될 때까지 시도 의 매커니즘으로 하고있는데, 이러면 실력이 늘지 않는 것 같네요..

실전도 아닌데 시간에 쫓기는 기분으로 풀었는데, 내일부터는 시간에 쫓기지 않고 내 코드에 대한 이해를 깊게 해보는 작업을 해봐야겠어요

푸는 시간을 줄이고, 결과 본 뒤 분석하는 시간을 갖는걸로!