10942번: 팰린드롬? (acmicpc.net)
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 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을 출력한다.
예제 입력 1
7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7예제 출력 1
1
0
1
1풀이
다이나믹 프로그래밍 문제.
(1) 각 질문마다 팰린드롬을 판별하여 저장하는 방법
(2) 수열의 모든 팰린드롬을 확인하여 저장하고 그 후에 판별하는 방법
2가지로 풀어보았다.
2000 x 2000 2차원 배열 check_palindrome을 만든다.
첫 번째 풀이 방법에서는 check_palindrome의 모든 값을 -1로 초기화해줬다.
질문을 하나씩 확인한다. 만약 x, y가 질문으로 들어왔다면, check_palindrome[x][y]를 확인한다. 0 또는 1이라면, 바로 결과를 return하여 저장하고, -1이라면 아직 판별되지 않았으므로 판별을 시작한다. x ~ y가 팰린드롬인지 확인한 후,
check_palindrome[x][y]부터,
check_palindrome[x + n][y - n] (x + n == y - n || (x + n) + 1 == y - n)까지
모두 팰린드롬이므로 모두 1로 바꿔준다.
두 번째 풀이 방법에서는
check_palindrome[x][y]를 모두 0으로 초기화해준다. index를 모두 돌면서, now_index로부터 down_index를 --, up_index를 ++해주면서 같지 않을 때까지 확인한다.
down = now, up = now일 때 뿐 아니라 짝수 개수의 팰린드롬도 확인해야 하므로
donw = now, up = now + 1로도 같은 방식으로 한 번 더 확인해준다.
첫 번째 방법은 340ms가 나왔고,
두 번째 방법은 236ms가 나왔다.
주의!!
cin의 횟수가 100만 번으로 매우 많아서 cin을 그냥 사용했더니 자꾸 시간 초과가 떴다 ㅜ-ㅜ 맞게 풀었는데도 틀린 줄 알고 한참을 찾아보다가 ios::sync_with_stdio(false);구문을 사용하면 된다는 것을 알게 되었다. 알고리즘 문제를 풀 때는 사용하도록 해야겠다.
코드
1. question 단위로 확인
#include <iostream>
using namespace std;
void input_data(void);
void palindrome(void);
void print_result(void);
int is_palindrome(int index);
void print_square(void);
int size_of_sequence, number_of_questions;
pair<int, int> questions[1000000];
int sequences[2001];
int check_palindrome[2001][2001];
int result[1000000];
int main(void)
{
ios::sync_with_stdio(false);
input_data();
palindrome();
print_result();
return (0);
}
void input_data(void)
{
cin >> size_of_sequence;
int i = 0;
while (++i <= size_of_sequence)
cin >> sequences[i];
cin >> number_of_questions;
i = -1;
while (++i < number_of_questions)
{
int a, b;
cin >> a >> b;
questions[i] = make_pair(a, b);
}
fill(check_palindrome[0], check_palindrome[2000], -1);
return;
}
void palindrome(void)
{
int i = -1;
while (++i < number_of_questions)
result[i] = is_palindrome(i);
return;
}
int is_palindrome(int index)
{
// print_square();
int front_index = questions[index].first;
int back_index = questions[index].second;
if (check_palindrome[front_index][back_index] == 1) // is palindrome
return (1);
else if (check_palindrome[front_index][back_index] == 0) // is not palindrome
return (0);
else // unknown
{
int i = -1;
int half_of_diff = (back_index - front_index) / 2;
while (++i <= half_of_diff)
{
if (sequences[front_index + i] != sequences[back_index - i])
{
check_palindrome[front_index][back_index] = 0; // when is not palindrome
return (0);
}
}
// when is palindrome
i = -1;
while (++i <= half_of_diff)
check_palindrome[front_index + i][back_index - i] = 1;
return (1);
}
return (-1);
}
void print_result(void)
{
int i = -1;
while (++i < number_of_questions)
cout << result[i] << '\n';
return;
}
void print_square(void)
{
int i = 0;
while (++i <= size_of_sequence)
{
int j = 0;
while (++j <= size_of_sequence)
cout << check_palindrome[i][j] << ' ';
cout << '\n';
}
cout << '\n';
return;
}2. 모든 수열을 먼저 확인
#include <iostream>
using namespace std;
void input_data(void);
void palindrome(void);
void print_result(void);
int is_palindrome(int index);
void print_square(void);
void check_all_index(void);
int size_of_sequence, number_of_questions;
pair<int, int> questions[1000000];
int sequences[2001];
int check_palindrome[2001][2001];
int result[1000000];
int main(void)
{
ios::sync_with_stdio(false);
input_data();
palindrome();
print_result();
return (0);
}
void input_data(void)
{
cin >> size_of_sequence;
int i = 0;
while (++i <= size_of_sequence)
cin >> sequences[i];
cin >> number_of_questions;
i = -1;
while (++i < number_of_questions)
{
int a, b;
cin >> a >> b;
questions[i] = make_pair(a, b);
}
fill(check_palindrome[0], check_palindrome[2000], 0);
return;
}
void palindrome(void)
{
check_all_index();
int i = -1;
while (++i < number_of_questions)
result[i] = is_palindrome(i);
return;
}
int is_palindrome(int index)
{
// print_square();
int front_index = questions[index].first;
int back_index = questions[index].second;
if (check_palindrome[front_index][back_index] == 1) // is palindrome
return (1);
else // is not palindrome
return (0);
}
void print_result(void)
{
int i = -1;
while (++i < number_of_questions)
cout << result[i] << '\n';
return;
}
void print_square(void)
{
int i = 0;
while (++i <= size_of_sequence)
{
int j = 0;
while (++j <= size_of_sequence)
cout << check_palindrome[i][j] << ' ';
cout << '\n';
}
cout << '\n';
return;
}
void check_all_index(void)
{
int now_index = 0;
while (++now_index <= size_of_sequence)
{
check_palindrome[now_index][now_index] = 1;
int down_index = now_index;
int up_index = now_index;
while (--down_index >= 1 && ++up_index <= size_of_sequence
&& sequences[down_index] == sequences[up_index])
check_palindrome[down_index][up_index] = 1;
down_index = now_index + 1;
up_index = now_index;
while (--down_index >= 1 && ++up_index <= size_of_sequence
&& sequences[down_index] == sequences[up_index])
check_palindrome[down_index][up_index] = 1;
}
return ;
}
야호~~!!🥰🥰🥰
