백준 10942번

오늘 풀어본 문제는 백준의 10942번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 $N$ 개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 $M$ 번 한다.

각 질문은 두 정수 $S$ 와 $E$ $(1 \leq S \leq E \leq 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$ 은 팰린드롬이다.

자연수 $N$ 개와 질문 $M$ 개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 $N$ $(1 \leq N \leq 2,000)$ 이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 $100,000$ 보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 $M$ $(1 \leq M \leq 1,000,000)$ 이 주어진다.

넷째 줄부터 $M$ 개의 줄에는 홍준이가 명우에게 한 질문 $S$ 와 $E$ 가 한 줄에 하나씩 주어진다.

출력

총 $M$ 개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 $1$ , 아닌 경우에는 $0$ 을 출력한다.

풀이과정

1번째 시도

이 문제는 DP를 이용하여 해결할 수 있는 문제이다. 팰린드롬은 한국어로 ‘회문’으로 앞으로 읽으나 뒤로 읽으나 같은 문장을 의미한다. 예를 들면, ‘다큰도라지일지라도큰다’ 같은 것이 있다.

이 문제에서는 문장을 입력받는 것은 아니지만 수열을 문장처럼 생각하여 회문을 알아낼 수 있다. 예를 들어 ‘12345654321’ 같은 수열은 회문이라고 할 수 있을 것이다.

이러한 회문의 구조를 자세히 살펴보면, 회문이 만들어지는 방식이 어떤 문자 ‘ $A$ ’ (진짜 문자 A가 아니라, 임의의 문자를 나타내기 위한 기호이다.) 와 임의의 회문 $B$ 에 대하여, $A(B)A$ 형태로 구성되어 있다는 것을 알 수 있다. 이를 이용하여 다음과 같이 점화식을 구성할 수 있다.

$DP$ 는 이차원 배열 형태로 구성되며, $DP[i][j]$ 는 $i \leq j$ 에 대하여 주어진 수열의 $i$ 번째 수에서 $j$ 번째 수로 구성된 수열이 회문인지 ( $1$ ) 아닌지 ( $0$ ) 여부를 저장한다고 하자. 또한 $A[i]$ 를 수열의 $i$ 번째 수라고 하자.

$DP[i][i] = 1$ 이다.
$A[i] = A[i + 1]$ 이면 $DP[i][i+1] = 1$ 이다.
$A[i] = A[j]$ 이고, $DP[i + 1][j - 1] = 1$ 이라서 $i$ 번째와 $j$ 번째 사이의 수열이 회문이라면, $DP[i][j] = 1$ 이다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

bool dp[2001][2001] = { 0, };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N;

	vector<int> arr(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= N; i++) {
		dp[i][i] = true;
		if (i < N) {
			if (arr[i] == arr[i + 1]) {
				dp[i][i + 1] = true;
			}
		}
	}

	for (int interval = 2; interval <= N - 1; interval++) {
		for (int i = 1; i <= N - interval; i++) {
			int j = i + interval;
			if (arr[i] == arr[j] && dp[i + 1][j - 1] == true) {
				dp[i][j] = true;
			}
		}
	}

	cin >> M;

	for (int query = 0; query < M; query++) {
		int start, end;
		cin >> start >> end;

		if (dp[start][end] == true) {
			cout << 1 << "\n";
		}
		else {
			cout << 0 << "\n";
		}
	}

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

이 문제는 CLASS 5 문제였고 DP를 이용한 문제였다. 확실히 CLASS 4의 DP 문제들 보다는 좀 더 생각을 많이 해야하는 문제인 것 같다. 아마 CLASS 5 에서는 이제까지 배운 내용 (세미나에서 나오는 수준의 고급 내용을 제외하고) 을 제대로 이용하는 동시에 사고력을 요하는 문제들이 많이 나올 것 같다는 느낌이 든다. 이번 CLASS를 끝낼 때 쯤이면 배경 지식의 간극이 어느 정도 보완이 되지 않을까 하는 생각이 든다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/10942

← Previous Post Next Post →