기타리스트

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp[N - 1] 에서 최댓값 찾아서 출력

문제 풀이 step 1

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

문제 풀이 step 2

  • dp[N][k] = 이전의 볼륨에서 V[N] 을 더하거나 빼서 나온 볼륨 k 를 사용할 수 있는지 없는지
    • dp[N][10] = 이전의 볼륨에서 V[N] 을 더하거나 빼서 나온 볼륨 10 을 사용할 수 있는지 없는지
    • dp[N][10] = 1 이라면 볼륨 10 을 사용할 수 있고, dp[N][10] = 0 이라면 볼륨 0 을 사용할 수 없다는 뜻
  • DP 의 특징인 “작은 문제의 해답으로부터 큰 문제의 해답을 찾는다” 를 이용합니다.
  • 점화식은 다음과 같습니다.
    • if (dp[N - 1][k] === 0) continue;
    • if(0 <= k - V[N]) dp[N][k - V[N]] = 1;
    • if(k + V[N] <= M) dp[N][k + V[N]] = 1;
  • 점화식을 위와 같이 작성한 이유는 다음과 같습니다.
    • 이전에 사용한 볼륨들에 대해서 현재 바꿀 수 있는 볼륨으로 바꿀수 있는 경우는
    • 뺐는데 0 보다 같거나 큰 경우, 더했는데 M 보다 같거나 작은 경우 이렇게 2 가지로 나눌 수 있습니다.
    • 따라서 두 경우에 대해서만 값을 계산해주면 됩니다.
  • base 값은 초기 볼륨의 값에 대해서 위의 점화식을 적용한 값이고, 그 이후로는 점화식을 이용해서 dp 배열을 모두 채우면 됩니다.
  • 그리고나서 dp[n - 1] 을 모두 순회하며, 만들 수 있는 볼륨 중에서 최댓값을 반환하고 만들 수 있는 볼륨이 없었다면 -1 을 반환하면 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 본 문제는 완전 탐색 문제의 성향을 많이 띄고 있는 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [N, S, M] = input[0].split(" ").map(Number);
	const V = input[1].split(" ").map(Number);

	const dp = Array.from(Array(N), () => Array(M + 1).fill(0));

	// base
	if (0 <= S - V[0]) dp[0][S - V[0]] = 1;
	if (S + V[0] <= M) dp[0][S + V[0]] = 1;

	// bottom-up
	for (let i = 1; i < N; i++) {
		for (let j = 0; j < M + 1; j++) {
			if (dp[i - 1][j] === 0) continue;

			if (0 <= j - V[i]) dp[i][j - V[i]] = 1;
			if (j + V[i] <= M) dp[i][j + V[i]] = 1;
		}
	}

	// 최댓값 찾기
	for (let i = M + 1; i >= 0; i--) {
		if (dp[N - 1][i] === 1) return i;
	}

	return -1;
};

console.log(solution(input));