🎲문제

---

주소:백준 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가 한 줄에 하나씩 주어진다.

✅ 풀이

---

풀이방법

다이나믹프로그래밍을 통해 해결하였다. 반복문과 while문을 사용하여 dp[i][i] 부터 dp[i-1][i+1] dp[i-2][i+2] 와 같이 순서대로 dp를 갱신 해주고 짝수개의 팰린드롬 수의 경우에는 dp[i][i+1], dp[i-1][i+2], dp[i - 2][i + 3] 순서대로 갱신시키는 방식으로 작성하였다.

1. N의 값을 입력받는다.
2. 전체 숫자 배열을 저장한다.
3. 저장된 숫자로 dp를 작성하는 solve함수를 실행시킨다.
4. 질문의 숫자인 M을 입력받는다.
5. 작성된 dp로 답을 출력하기위해 질문인 x와 y을 받는다.
6. 저장된 dp[x][y]의 값을 순서대로 출력한다.

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

	solve();

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

1. 가장 먼저 숫자가 하나인 경우와 두 개인데 팰린드롬의 숫자인 경우를 받아 dp에 1을 저장시켰다.
2. 전체 배열을 순회해야 하므로 배열의 크기만큼 반복문을 생성한다.
3. 범위를 통해 dp를 작성하기위해 range변수를 추가한다.
   1. 3에서 3, 2에서 4, 1에서 5 와 같이 사용하기 위함
4. 범위를 초과하면 끝나는 while문을 작성한다. dp의 경우 dp[x-range][y+range]일 때, arr[x-range] == arr[y+range]이고, dp[x-range+1][y+range-1] 이 true라면 true를 저장하는 방식으로 작성한다.
5. 팰린드롬의 수가 홀수일 경우 뿐만아니라 짝수일 경우도 작성해주어야한다. 그러므로 dp[x-range][y+range+1]인 경우도 while문 하나를 더생성하여 만들어준다.
6. 전체를 반복하면 전체 팰린드롬 수의 정보가 담긴 dp테이블이 완성된다

void solve() {

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

	for (int i = 1; i <= N; i++) {
		int range = 1;
		
		while (i - range > 0 && i + range <= N) {

			if (arr[i-range] == arr[i+range] && dp[i-range+ 1][i+range - 1] == 1)
				dp[i-range][i+range] = true;

			range++;
		}
		range =  1;
		while (i - range > 0 && i + range+1 <= N) {

			if (arr[i - range] == arr[i + range +1] && dp[i - range + 1][i + range] == 1)
				dp[i - range][i + range+1] = true;

			range++;
		}
	}
}

전체 코드

#include<iostream>

using namespace std;

int N, M;
int arr[2001] = {0, };
bool dp[2001][2001] = {0, };

void init();
void solve();

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

	solve();

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

void solve() {

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

	for (int i = 1; i <= N; i++) {
		int range = 1;
		
		while (i - range > 0 && i + range <= N) {

			if (arr[i-range] == arr[i+range] && dp[i-range+ 1][i+range - 1] == 1)
				dp[i-range][i+range] = true;

			range++;
		}
		range =  1;
		while (i - range > 0 && i + range+1 <= N) {

			if (arr[i - range] == arr[i + range +1] && dp[i - range + 1][i + range] == 1)
				dp[i - range][i + range+1] = true;

			range++;
		}
	}
}

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

	init();

	return 0;
}