[Python] 10942.팰린드롬?(골4) / DP

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

10942번: 팰린드롬?

---

2. 핵심 아이디어

 

이 문제가 DP 유형에 있다는 것에 많은 고심을 했다.

결국 아이디어를 떠올리지 못했고,

다른 블로그의 아이디어를 참고해 문제를 풀었다.

 

그러나, 아이디어를 본 순간 DP의 본질적인 부분

즉, 작은 문제의 해결법이나 관계가 큰 문제의 해결법으로 이어진다는 원리가

잘 녹아든 문제라는 생각이 들었다.

 

기존에 우리가 팰린 드롬을 확인할 때 어떻게 판단했을까?

우리는 첫문자와 마지막 문자를 차례대로 비교하며

안쪽 문자열까지 전체 문자열을 순차적으로 비교했다.

bool isPalindrome(string s) {
	int size = s.size();

	for(int i = 0; i< size/2; i++) {
		if(s[i] != s[size-1-i])
			return false;
	}

	return true;
}

 

 

이를 추상화하면 팰린드롬 판단을 위해서는

양 끝문자를 비교하는 과정을 이용한다.

 

 

출처 : https://velog.io/@himi/%EB%B0%B1%EC%A4%80-10942.-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC

 

그렇다면 

첫문자와 끝문자를 제외한 [start+1 부터 end-1]까지가 팰린드롬이라면

start와 end 자리의 문자만 같으면 팰린드롬이라 판단할 수 있다.

 

또한 이를 반대로 해석한다면

첫문자와 끝문자가 같다면,

[start+1 부터 end-1]의 문자열이 팰린드롬이면,

이 문자열은 팰린드롬이라 판단할 수 있다.

 

즉,

[ (문자1) + 팰린드롬 문자열 + (문자2) ] 의 상황에서

문자1 ==문자2이기만 하다면 이 문자열은 팰린드롬 문자열이며

 

[(문자1) + 문자열 + (문자1)]의 상황에서

가운데 문자열이 팰린드롬이라면 이 문자열은 팰린드롬 문자열이다.

 

---

 

그럼 이 원리를 이용해 DP를 어떻게 만들까?

 

아이디어는 start와 end 문자열의 팰린드롬 여부를 기록한 DP를 메모제이션하는 것이다.

 

그러나, 여기서 문제가 발생한다.

만약 2차원 배열을 순차적으로 돌며 배열을 채워나간다면

참고를 해야할 DP칸이 채워지지 않은 상황이 발생하기 때문이다. 

start/end	0	1	2	3	4
0
1					?
2				X
3
4
5

 

예를 들어 순차적으로 2차원 배열을 돌며

dp[1][4]의 팰린드롬 여부를 판단하는 상황을 생각해보자

 

start=1 /  end= 4 이고 start와 end 인덱스의 숫자가 같다면

dp[start+1][end-1]이 팰린드롬인지를 참고해야 한다.

 

그런데 dp[2][3]은 순차적으로는 아직 채워지지 않은 칸이다.

따라서 판단을 할 수가 없다.

 

따라서 대각선 밑으로, 밑에서부터 dp를 채워야 한다.

start/end	0	1	2	3	4
0	1	2	3	4	5
1		1	2	3	4
2			1	2	3
3				1	2
4					1
5

=> 채우는 우선순위를 표현한 표

 

이를 위해 number_len를 0부터 n-number_len까지 돌며

밑에서부터 차례대로 채워나가는 코드를 완성했다.

for number_len in range(n):
  for start in range(n-number_len):
    end = start+number_len

 

---

##분기사항

 

마지막으로 몇가지 분기사항이다.

1. 글자가 한글자라면(start==end) => 무조건 팰린드롬

2. 글자가 두글자라면 (start==end-1) => 두 숫자가 같으면 팰린드롬

3. 글자가 세글자 이상이라면 => 양끝 숫자가 같고 + 가운데가 팰린드롬이라면 팰린드롬

 

여기서 두글자인 경우를 고려해주는 이유는

세글자 이상에서는 dp[start+1][end-1]을 참고해 팰린드롬을 판단하는데

두글자라면 start+1과 end-1이 엇갈리기 때문이다.

 

예를 들어 start=2 / end=3인 두글자에서는

start+1은 3 / end-1은 2가 되어 엇갈린다.

 

따라서, number[start]==number[end]인지만 판단해주면 된다.

---

3. 코드

import sys

#input= lambda: sys.stdin.readline().strip('\n')
n= int(input())
numbers= list(map(int, input().split()))
q= int(input())

dp=[[0]*n for _ in range(n)]

for number_len in range(n):
  for start in range(n-number_len):
    end = start+number_len
    # 한글자일 때
    if start==end :
      dp[start][end]=1
    
    #양 끝 두 숫자가 같고 가운데도 팰린드롬일때 or 두글자가 같을 때
    elif numbers[start]==numbers[end] :
      if number_len==1 or dp[start+1][end-1]:
        dp[start][end]=1

for _ in range(q):
  s,e= map(int, input().split())
  print(dp[s-1][e-1])

---

4.배운 점

dp는 항상 풀이를 보면 쉬운데 그 풀이를 생각해내는게 어려운 것 같다.

큰 문제를 divide 해내는 시각을 가진 이들을 보면 이제 존경스럽다..

 

이 문제는 단순 dp적 사고를 하는 것에서 그치지 않고

어떻게 for문을 탐색해나아갈 것인가? 라는 질문도 던졌어야 했다.

 

또한, 몇가지 분기사항도 고려해주어야 해서 나에겐 너무 까다로웠던 문제이다.

 

그러나, 팰린드롬 판단 알고리즘의 추상화 => 양 끝 문자열 탐색 과 같은 사고는

앞으로 dp문제를 접근할 때 한번쯤 떠올려볼만한 원리라 생각했다.