[Algorithm] BOJ 팰린드롬? - 10942번

 

 

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] = ;
	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;
}

3. 채점 기록

 

메모리 : 17528KB / 시간 : 316ms

 

---

 

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?