BOJ(C++) / 백준 10942 : 팰린드롬?

백준 10942 : 팰린드롬?

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

10942번: 팰린드롬?

 

문제

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

먼저, 홍준이는 자연수 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은 팰린드롬이다.

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

 

입력

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

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

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

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

 

출력

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

 

코드

//백준 팰린드롬? 10942
#include <iostream>
#include <vector>

using namespace std;

vector<int> v;
int S, E;
int dp[2001][2001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	v.push_back(0);
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	//길이 1
	for (int i = 1; i <= N; i++) {
		dp[i][i] = 1;
	}
	//길이 2
	for (int i = 1; i < N; i++) {
		if(v[i] == v[i+1]) //첫번째 수와 두번째 수가 같을 때
			dp[i][i + 1] = 1;
	}
	//길이 3이상
	for (int i = 2; i < N; i++) { //length
		for (int j = 1; j <= N-i; j++) { //left
			if (v[j] == v[i + j] && dp[j + 1][i + j - 1])
				dp[j][i + j] = 1;
		}
	}

	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int S, E;
		cin >> S >> E;
		cout << dp[S][E] << "\n";
	}

	return 0;
}

 

설명

이번 문제는 시간 제한이 관건이기 때문에 DP를 이용하여 구현한다.

길이가 1일 때 2일 때 3 이상일 때로 나눠서 구현한다.

길이가 1일 때는 모두 팰린드롬이므로 dp배열에 1을 저장한다.

길이가 2일 때는 첫번째 수와 두 번째 수를 비교하여 수가 같을 때 dp 배열에 1을 저장한다.

길이가 3이상일 때는 양 끝을 제외한 그 사이가 팰린드롬이고 양 끝의 수가 같을 때 dp 배열에 1을 저장한다. 

S, E를 입력받아 dp배열의 값을 출력한다. 

고찰

이번 문제는 구글링으로 문제를 해결할 수 있었다.

이전에 풀었던 팰린드롬과는 다르게 시간제한이 0.5초로 매우 짧았기 때문에 dp로 구현해야 한다.

당연히 모든 팰린드롬을 구하는 것보다 그때 그때 입력받아 구하는 것이 더 짧을 거라고 생각했던 게 착오였다.

 

시간 초과 난 코드

//백준 팰린드롬? 10942
#include <iostream>
#include <vector>

using namespace std;

//시간 초과
vector<int> v;
int S, E;

bool palindrome(int left, int right) {

	while (S <= left) {
		if (v[left] != v[right])
			return false;
		left--;
		right++;
	}
	return true;
}

int main() {
	//입출력 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> S >> E;
		//길이 홀수 
		if ((E - S) % 2 == 0) {
			if (palindrome((E + S) / 2 - 2, (E + S) / 2) == true)
				cout << "1\n";
			else
				cout << "0\n";
		}
		//길이 짝수
		else {
			if(palindrome((E + S) / 2 - 1, (E + S) / 2) == true)
				cout << "1\n";
			else
				cout << "0\n";
		}
	}
	return 0;
}

 

난이도

Gold 3