BOJ_10942_팰린드롬?

이번 문제는 팰린드롬에 대해서 풀어보겠습니다.

팰린드롬은 데칼코마니 형태의 숫자나 문자를 나타내는 문제로 유형은 크게 

입력된 내용이 팰린드롬인지 여부와 입력된 내용을 팰린드롬으로 만드는 방법 

이렇게 두 가지입니다.

이번 포스팅에서는 팰린드롬인지 여부를 파악하는 방법으로 DP 방식을 활용하여 풀겠습니다. 

푸는 방식은 Bottom-Up 방식을 사용해서 풀겠습니다. 

사실 Top-Down 방식이 더 간단하고 쉽긴 하지만, 개인적으로 이번 문제는 Bottom-Up 방식이 더 어렵고

Bottom-Up 방식을 안다면 Top-Down 도 쉽게 풀 수 있을 것이라 생각하여 결정하였습니다.

우선 점화식부터 세워보면 D[i][j]는 i부터 시작해서 j까지의 숫자 중 팰린드롬이 맞는지 여부를 파악한다고

정의할 수 있습니다.

점화식을 세울 때 나올 수 있는 경우의 수는 크게 3가지입니다.

첫 번째로는 시작점과 종료점이 같을 경우입니다. 

i == j일 경우는 반드시 팰린드롬이어야만 합니다. 

가령 3이라는 숫자를 볼 때 처음 시작할 때도 3이고 마지막도 3이기 때문에 

팰린드롬이라고 말할 수 있습니다.

두 번째로는 시작점과 종료점이 하나 차이일 경우입니다.

i+1 == j 일 경우 해당 위치의 값 A[i]와 A[j]가 같을 경우 d[i][j]는 팰린드롬이라고 표현할 수 있습니다.

마지막으로는 시작점과 종료점이 둘 이상 차이날 경우입니다.

i+k == j 일 때이며, 팰린드롬이 성립하기 위해서는 시작점에서의 값 A[i]와 

종료점에서의 값 A[j]이 같아야 합니다. 

그리고 d[i][j]가 팰린드롬이기 위해서는 앞서 발생하는 d[i+1][j-1]인 경우도 팰린드롬이어야 하므로

이 두 조건을 모두 체크한 뒤에 d[i][j] = '팰린드롬'  이라고 정의할 수 있습니다.

따라서 코드는 다음과 같습니다.

---

* 선언부 * 

---

private static Scanner scanner;

private static boolean[][] d;  // 팰린드롬 여부를 파악

private static int[] a;           // 해당 위치에 들어갈 값

---

* 구현부 * 

---

scanner = new Scanner(System.in);

int n = scanner.nextInt();

a = new int[n + 1];

for (int i = 1; i <= n; i++)

a[i] = scanner.nextInt();

d = new boolean[n + 1][n + 1];

for (int i = 1; i <= n; i++) {

d[i][i] = true;

}

// --> 시작점과 종료점이 같을 경우 모두 팰린드롬!

for (int i = 1; i < n; i++) {

if (a[i] == a[i + 1])

d[i][i + 1] = true;

}

// --> 시작점과 종료점이 길이 하나 차이 날 경우 그 값이 같은지 체크 한 뒤 같으면 팰린드롬이라고 정의

for (int k = 2; k <= n; k++) {

for (int i = 1; i <= n - k; i++) {

int j = k + i;

if (a[i] == a[j] && d[i + 1][j - 1]) {

d[i][j] = true;

}

}

}

// 시작점과 종료점의 길이가 2이상 날 경우이므로 k가 2부터 시작하게 됩니다. 길이 차이는 최대 n까지

// 발생할 수 있으며 j값은 시작점과 시작점으로부터 종료점까지의 길이의 합입니다.

// 다음 두 반복문을 설정한 뒤 기존 조건대로 시작점과 종료점에서의 값을 비교합니다.

// 이 두 값이 같아야하며 동시에 이 전 경우도 팰린드롬이어야 합니다.

// 두 조건이 모두 성립할 경우 현재 i의 시작점에서 j의 종료점까지인 경우도 

// 팰린드롬이라고 정의할 수 있습니다.

---

전체 코드는 다음과 같습니다.

---

import java.util.Scanner;

public class 팰린드롬_2 {

private static Scanner scanner;

private static boolean[][] d;

private static int[] a;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int n = scanner.nextInt();

// a 갯수

a = new int[n + 1];

for (int i = 1; i <= n; i++)

a[i] = scanner.nextInt();

d = new boolean[n + 1][n + 1];

for (int i = 1; i <= n; i++) {

d[i][i] = true;

}

for (int i = 1; i < n; i++) {

if (a[i] == a[i + 1])

d[i][i + 1] = true;

}

for (int k = 2; k <= n; k++) {

for (int i = 1; i <= n - k; i++) {

int j = k + i;

if (a[i] == a[j] && d[i + 1][j - 1]) {

d[i][j] = true;

}

}

}

int t = scanner.nextInt();

// test case

while (t-- > 0) {

int s = scanner.nextInt();

int e = scanner.nextInt();

if (d[s][e]) {

System.out.println(1);

} else {

System.out.println(0);

}

}

}

}

---

감사합니다.