직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.
10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
생각의 흐름
생각보다 간단한 DP 문제이다.
1) 길이가 1인 경우
모두 팰린드롬 수가 된다.
2) 길이가 2인 경우
바로 다음 칸의 수와 비교해서 같은지 확인하면 된다.
3) 길이가 3 이상인 경우
우리의 배열 input이 다음과 같다 해보자.
1 2 1 3 1 2 1
이중 가장 중간에 있는 P : [1, 2, 1] 은 팰린드롬 수 이다. 앞으로 읽으나, 뒤로 읽으나 같은 수가 나오기 때문이다.
이 팰린드롬 수를 P 라고 하면 2 p 2 또한 팰린드롬 수가 된다.
따라서 DP[i][j] = DP[i+1][j-1]이 될 것 이다.
나의 코드
#include <bits/stdc++.h>
using namespace std;
#define MAX 2001
int N, M;
int arr[MAX];
int DP[MAX][MAX];
vector<pair<int, int>> vec;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> arr[i];
}
cin >> M;
for(int i = 0; i < M; i++){
int from, to;
cin >> from >> to;
vec.push_back({from, to});
}
for(int i = 1; i <= N; i++) {
DP[i][i] = 1; // 길이가 1인 경우
}
for(int i = 1; i < N; i++) {
if(arr[i] == arr[i+1]){
DP[i][i+1] = 1; // 길이가 2인 경우
}
}
for(int i = 2; i < N; i++) { // 차이 나는 칸의 수
for(int j = 1; j <= N-i; j++) {
if(arr[j] == arr[j+i] && DP[j+1][j+i-1]) {
DP[j][j+i] = 1;
}
}
}
for(int i = 0; i < M; i++) {
cout << DP[vec[i].first][vec[i].second] << "\n";
}
return 0;
}
'Algorithm > 백준' 카테고리의 다른 글
[백준][C++] 1202번: 보석 도둑 <214> (0) | 2022.04.25 |
---|---|
[백준][C++] 12015번: 가장 긴 증가하는 부분 수열 2 <213> (0) | 2022.04.24 |
[백준][C++] 1005번: ACM Craft <211> (0) | 2022.04.06 |
[백준][C++] 1766번: 문제집 <210> (0) | 2022.04.05 |
[백준][C++] 2166번: 다각형의 면적 <209> (0) | 2022.04.04 |
댓글