1. 문제 풀이
팰린드롬? 문제는 자연수 N 안에서 S번째와 E번째 수까지 팰린드롬, 곧 거꾸로 읽어도 제대로 읽는 것과 동일한지 알아내는 문제이다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
우선 S부터 E사이의 차를 거리라 부르고 S와 E의 사이의 결과를 담을 이차원배열을 N*N 크기로 생성했다.
펠린드롬의 패턴은 S와 E 보다 1씩 줄어든 거리가 팰린드롬이고 S와 E가 같으면 팰린드롬이 되는 규칙을 이용해 하나씩 1로 채워가는 방식으로 풀이하였다.
거리가 0, 곧 같은 인덱스 일때는 1로 모두 초기화를 하고 거리가 1일때 j , j+1이 같으면 1로 설정했다.
거리가 2이상일때는 거리를 j , 대상인덱스를 z 로 while 문을돌려가며 z / j + z 가 같고 그 안에 직전 값이 1이면 1을 넣도록, 그리고 j + z 가 마지막 인덱스가 되면 j ++로 거리를 늘려갔다.
2. 코드
#include <iostream>
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[])
{
int m, x, y;
int answer;
scanf("%d", &m);
int n[m][m] = {0,};
int arr[m];
for (int j = 0; j < m; j++)
scanf("%d", &arr[j]);
//거리가 0일때
for (int i = 0; i < m; i++)
n[i][i] = 1;
//거리가 1일때
for (int j = 0; j < m - 1; j++)
{
if (arr[j] == arr[j + 1])
n[j][j + 1] = 1;
}
int j = 2;
int z = 0;
//거리가 2이상일때
while (j < m)
{
if (arr[z] == arr[z + j] && n[z + 1][z + j - 1])
n[z][z + j] = 1;
//마지막 인덱스까지 체크했을 시 j++로 거리늘려 체크
if (z + j == m - 1)
{
j++;
z = -1;
}
z++;
}
scanf("%d", &answer);
for (int i = 0; i < answer; i++)
{
scanf("%d %d", &x, &y);
printf("%d\n", n[x - 1][y - 1]);
}
return 0;
}
C++
복사
3. 채점 기록
메모리 : 17528KB / 시간 : 316ms
