[C++] 백준(BOJ) - 10942 : 팰린드롬?
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 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을 출력한다.
알고리즘
- DP (Bottom Up)
풀이
- 브루트 포스
- $_nC_2 \times n$ 약 40억의 시간 복잡도
- dp를 활용해 점화식을 만들기
- dp[i][j] : i부터 j까지 팰린드롬일 경우 dp에 1 대입
- 자기 자신은 팰린드롬이다
- 바로 옆의 수가 같으면 팰린드롬이다
- i와 j 사이의 수가 팰린드롬이고 i와 j가 같으면 팰린드롬이다
코드
// BOJ - 10942 : 팰린드롬?
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int n, m, s, e, a[2004], dp[2004][2004];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) dp[i][i] = 1;
for (int i = 1; i <= n; i++)
{
if (a[i] == a[i + 1]) dp[i][i + 1] = 1;
}
for (int _size = 2; _size <= n; _size++)
{
for (int i = 1; i <= n - _size; i++)
{
if (a[i] == a[i + _size] && dp[i + 1][i + _size - 1]) dp[i][i + _size] = 1;
}
}
cin >> m;
while (m--)
{
cin >> s >> e;
cout << dp[s][e] << "\n";
}
return 0;
}
평가
- Bottom-up 방식의 DP 문제 풀이
- 점화식을 만드는 과정이 쉽지는 않지만 조건에 맞춰 하나 하나 해결해 나갈 경우 Top-down 방식보다 간단하게 풀이가 가능한 경우도 있다
- 시작점과 끝지점을 상태값으로 정의한다는 아이디어
