연속합 2

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[0][n] = n 번째 수가 마지막으로 오는 연속합 중의 가장 큰 합
  • dp[1][n] = n 번째까지의 수열 중에서 수를 하나 제거한 경우에서 가장 큰 연속합
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 백준 1912번 - 연속합 풀이의 내용을 이용해서 풀 수 있습니다.
  • 정의한 dp를 보면 수를 제거하지 않는 경우와 수를 무조건 하나 제거하는 경우로 나눴습니다.
  • 각 경우는 어떻게 성립이 되는지 알아보겠습니다.
    • 수를 제거하지 않는 경우 (이전 연속합 풀이의 내용과 동일합니다.)
      • 이전의 수열과 연속하는 경우
        • dp[0][n] = dp[0][n - 1] + numArr[n]
      • 이전의 수열과 연속하지 않는 경우
        • dp[0][n] = numArr[n]
    • 수를 제거하는 경우 (이전 연속합 풀이에 추가된 내용입니다.)
      • n 번째 수를 제거하는 경우
        • dp[1][n] = dp[0][n - 1] (제거하지 않은 경우에 n 번째 수를 연속하지 않음)
      • n 번째 수를 제거하지 않는 경우
        • dp[1][n] = dp[1][n - 1] + numArr[n] (제거한 경우에 n 번째 수를 연속함)
  • 위의 모든 경우의 최대값을 구하면 정답이 됩니다.
  • 최종적으로 구한 배열에 Math.max 메소드를 이용하면 스택 오버플로우가 발생하니까 매 경우마다 최대값을 구해주는 방식을 이용하면 됩니다.

추가로 배운 점

  • Math.max 메소드의 입력 배열의 크기에 제한이 그렇게 크지 않다는 사실을 알게 되었습니다.
  • 크기 제한을 넘어갈 경우 스택 오버플로우가 발생합니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 다시 풀어도 또 당황을 했습니다.
  • 하지만, DP 문제의 경우 DP 배열을 채워나갈 때 채우는 방법의 모든 경우의 수를 생각해보면 해결할 수 있습니다.
  • 여러 문제를 풀어보고 얻을 수 있었던 팁입니다.

소스 코드

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

const solution = (input) => {
	const n = parseInt(input[0]);
	const numArr = input[1].split(" ").map(Number);
	const dp = [[], []];

	// base
	dp[0][0] = numArr[0];
	dp[1][0] = numArr[0];
	let max = numArr[0];

	// 수를 무조건 한 개 이상 선택해야 하므로 예외처리를 해준다.
	if (n > 1) {
		dp[0][1] = Math.max(numArr[1] + dp[0][0], numArr[1]);
		dp[1][1] = Math.max(numArr[1], dp[1][0]);
		max = Math.max(max, dp[0][1], dp[1][1]);
	}

	for (let i = 2; i < n; i++) {
		// 제거하지 않은 경우 (연속할지, 연속 안할지)
		dp[0][i] = Math.max(numArr[i] + dp[0][i - 1], numArr[i]);

		// 제거하는 경우 (현재 수를 제거하지 할지, 현재 수를 제거하지 않을지)
		dp[1][i] = Math.max(dp[0][i - 1], dp[1][i - 1] + numArr[i]);

		max = Math.max(max, dp[0][i], dp[1][i]);
	}

	return max;
};

console.log(solution(input));