땡글이LAB
[백준] 10942 팰린드롬? - C++ 본문
처음 문제를 접했을 때는 DP라는 생각이 들지 않고, 그냥 단순한 구현문제인 줄 알고 구현했더니 시간초과가 나왔다. 내가 짠 코드의 시간복잡도는 O(N * M) 이었다. (아래의 코드는 시간초과된 틀린 코드이다.)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M;
int board[2005];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> board[i];
}
cin >> M;
int S, E;
while (M--) {
cin >> S >> E;
if (S == E) {
cout << 1 << '\n';
continue;
}
bool isPal = true;
while (S < E) {
if (board[S] != board[E]) {
isPal = false;
break;
}
S++; E--;
}
if (isPal) cout << 1 << '\n';
else cout << 0 << '\n';
}
}
여기서 더 단축시키려면 이분탐색? DP? 등을 생각해보다가 이분 탐색은 말도 안되고 DP가 적당하다고 생각했다. 어떻게 DP로 이 문제를 풀까?
우선 DP 배열의 요소가 무엇을 의미하는지와 점화식을 세워둘 필요가 있다. S 번째 수부터 E 번째 수까지 팰린드롬을 물어보는 질문 수(M)이 1,000,000 이하이기 때문에 질문 수를 받는 반복문 안에서 뭔가 작업을 하면 안될 것 같다는 생각이 들어서,
- DP[S][E] : "S 번째 수부터 E 번째 수까지는 팰린드롬인가? 맞으면 1, 아니면 0"
라고 DP 배열 요소의 의미를 정해뒀다. 하지만, DP 배열 요소들간의 연결관계는 찾을 수 없었다. 하지만 DP 배열을 채우고 질문(M)을 받는 질문 반복문 안에서 다른 코드 없이 DP[S][E] 를 출력해준다면, 이전의 코드보다는 시간복잡도가 O(N^2)로 개선될 것이다. (N은 1,000 이하이고, M은 1,000,000 이하로 범위가 2배 이상 차이남)
그래서 작성한 코드이다. 시간초과나지 않고 통과하는 것을 확인할 수 있었다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M;
int board[2005];
int DP[2005][2005];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> board[i];
}
for (int i = 1; i <= N; i++) {
DP[i][i] = 1;
if (board[i - 1] == board[i]) DP[i - 1][i] = 1;
}
for (int gap = 2; gap < N; gap++) {
for (int i = 1; i <= N - gap; i++) {
int S = i, E = i + gap;
if (board[S] == board[E] && DP[S + 1][E - 1]) DP[S][E] = 1;
}
}
cin >> M;
while (M--) {
int S, E;
cin >> S >> E;
cout << DP[S][E] << '\n';
}
}
'Algorithm > Problem Solve' 카테고리의 다른 글
[백준] 13144 List of Unique Numbers - C++ (0) | 2022.02.09 |
---|---|
[백준] 2295 세 수의 합 - C++ (0) | 2022.02.07 |
[백준] 2805 나무 자르기 - C++ (0) | 2022.02.07 |
[프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT (0) | 2022.01.18 |
Comments