팰린드롬?

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp 배열을 이용해서 각 질문에 답하기

문제 풀이 step 1

  • 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 합니다.
  • 먼저, 홍준이는 자연수 N 개를 칠판에 적습니다. 그 다음, 명우에게 질문을 총 M 번 합니다.
  • 각 질문은 두 정수 S 와 E (1 <= S <= E <= N) 로 나타낼 수 있으며, S 번째 수부터 E 번째 까지 수가 팰린드롬을 이루는지를 물어보며,
  • 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 합니다.
  • 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1 라고 하면
    • S = 1, E = 3 인 경우 1, 2, 1 은 팰린드롬입니다.
    • S = 2, E = 5 인 경우 2, 1, 3, 1 은 팰린드롬이 아닙니다.
    • S = 3, E = 3 인 경우 1 은 팰린드롬입니다.
    • S = 5, E = 7 인 경우 1, 2, 1 은 팰린드롬입니다.

문제 풀이 step 2

  • dp[s][e] = 수열에서 s 번째 수부터 e 번째 까지 수가 팰린드롬인지 아닌지
  • DP 의 특징인 “작은 문제의 해답으로부터 큰 문제의 해답을 찾는다”를 이용합니다.
  • 점화식을 작성하려면 팰린드롬에 대해서 알아야 합니다.
    • 팰린드롬에 관해서는 백준 1259번 - 팰린드롬수 풀이 에 설명되어 있습니다.
    • 간단히 설명하자면, 앞에서부터 읽어도 뒤에서부터 읽어도 같은 수열을 의미합니다.
  • 팰린드롬의 특징과 DP 의 특징을 조합하면 점화식을 작성할 수 있습니다.
    • 예를 들어, 팰린드롬인 어떤 수열 k 가 있다고 가정하겠습니다.
      • 수열 k 가 팰린드롬이라면, “1 k 1” 과 같이 수열 k 의 앞과 뒤에 같은 수가 있다면, 이 수열도 팰린드롬입니다.
      • 마찬가지로 “1 k 1” 이 팰린드롬이라면, “2 1 k 1 2” 와 같이 수열 “1 k 1” 의 앞과 뒤에 같은 수가 있다면, 이 수열도 팰린드롬입니다.
      • 이렇게 작은 수열을 키워가며, 각각의 수열이 팰린드롬인지 확인할 수 있습니다.
    • 다른 예로, 팰린드롬이 아닌 어떤 수열 q 가 있다고 가정하겠습니다.
      • 수열 q 이 팰린드롬이 아니라면, “1 q 1” 과 깉이 수열 q 의 앞과 뒤에 같은 수가 있어도, 이 수열은 팰린드롬이 아닙니다.
      • 마찬가지로 “1 q 1” 이 팰린드롬이 아니니, “2 1 q 1 2” 도 팰린드롬이 아닙니다.
      • 이처럼 팰린드롬이 아닌 경우는 수열을 키워도 팰린드롬이 아니기 때문에 확인할 필요도 없습니다.

문제 풀이 step 3

  • 위의 내용을 바탕으로 점화식을 세워보면 다음과 같습니다.
    • 1 은 팰린드롬, 0 은 팰린드롬이 아님 을 나타냅니다.
    • 만약, dp[s][e] = 1 이고, arr[s - 1] = arr[e + 1] 이면, dp[s - 1][e + 1] = 1 입니다.
    • 만약, dp[s][e] = 0 이면, dp[s - 1][e + 1], dp[s - 2][e + 2], … 모두 0 입니다.
  • base 값은 다음과 같습니다.
    • dp 배열의 모든 값은 0 으로 채웁니다.
      • 만약 작은 수열이 팰린드롬이 아니라는 것이 판별이 나면, 그 수열을 키운 모든 수열은 팰린드롬이 아닙니다.
      • 팰린드롬이 아닌 수열을 키운 모든 수열에 대해서 이후의 로직을 멈추기 위해서 0 으로 채웁니다.
    • dp[0][0], dp[1][1], dp[2][2], … 모두 1 입니다.
      • 왜냐하면, 한 자리 수는 모두 팰린드롬이기 때문입니다.
  • base 값을 토대로 점화식을 이용해서 dp 배열을 채워가면 됩니다.
    • 수열을 키우는 방법도 두 가지로 나눌 수 있습니다.
    • “1”, “2 1 2”, “3 2 1 2 3”, … 과 같이 홀수 수열 키우기
    • “2 2”, “1 2 2 1”, “3 1 2 2 1 3”, … 과 같이 짝수 수열 키우기
  • dp 배열을 모두 채웠으면, 각 질문에 대해서 dp 배열을 이용해서 답변하면 되겠습니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const m = Number(input[2]);

	// dp 배열 모두 0 으로 초기화하기
	const dp = Array.from({length: n}, () => Array(n).fill(0));

	// base
	for (let i = 0; i < n; i++) {
		// 한 자리 수열은 모두 팰린드롬
		dp[i][i] = 1;
	}

	// bottom-up
	for (let i = 1; i < n - 1; i++) {
		// 홀수 키우기
		let [left, right] = [i - 1, i + 1];

		while (0 <= left && right < n) {
			if (arr[left] === arr[right]) dp[left][right] = 1;
			else break;

			left -= 1;
			right += 1;
		}
	}
	for (let i = 0; i < n - 1; i++) {
		// 짝수 키우기
		if (arr[i] === arr[i + 1]) dp[i][i + 1] = 1;
		else continue;

		let [left, right] = [i - 1, i + 2];
		while (0 <= left && right < n) {
			if (arr[left] === arr[right]) dp[left][right] = 1;
			else break;

			left -= 1;
			right += 1;
		}
	}

	let res = "";
	// dp 배열을 이용해서 각 질문에 답변하기
	for (let i = 3; i < 3 + m; i++) {
		const [s, e] = input[i].split(" ").map(Number);

		res += dp[s - 1][e - 1] + "\n";
	}

	return res;
};

console.log(solution(input));