백준 1695번 펠린드롬 만들기

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : DP

(0) 생각

 양끝에서 안쪽으로 좁혀 오면서 펠린드롬을 만드는 데 필요한 최소 개수를 세줍니다.

    1. 탐색하는 두 수가 같으면 그냥 다음 탐색으로 넘어갑니다.

    2. 탐색하는 두 수가 다르면, 한쪽을 맞춰주고, 그쪽만 넘어갑니다.

 예를 들어 다음과 같은 수열이 주어졌다고 합시다.

Index	0	1	2	3	4	추가 수
수열	1	2	3	4	2	0

 

 우리는 양 끝에서 탐색을 시작합니다.

Index	0	1	2	3	4	추가 수
수열	1	2	3	4	2	0

 탐색하는 두 수가 다르니, 한쪽을 맞춰주고 넘어가야 합니다.

 경우 1. 왼쪽 index를 넘어가는 경우

 오른쪽에 필요한 수를 추가해 주고 탐색하는 왼쪽 index를 다음으로 넘어갑니다.

Index	0	1	2	3	4	추가	추가 수
수열	1	2	3	4	2	1	1

 탐색하는 두 수가 같으므로 그냥 넘어갑니다. 

Index	0	1	2	3	4	추가	추가 수
수열	1	2	3	4	2	1	1

 (1-1) 왼쪽을 맞춰봅니다.

Index	0	1	2	3	추가	4	추가	추가 수
수열	1	2	3	4	3	2	1	2

    이때 탐색하는 index 가 왼쪽 = 오른쪽 이므로 탐색을 끝내고 답은 2가 됩니다.

 (1-2) 오른쪽을 맞춰봅니다.

Index	0	1	추가	2	3	4	추가	추가 수
수열	1	2	4	3	4	2	1	2

    마찬가지로 답은 2가 되겠죠.

 경우 2. 오른쪽 index를 넘어가는 경우

 왼쪽에 필요한 수 추가, 탐색하는 오른쪽 index를 다음으로 넘김

Index	추가	0	1	2	3	4	추가 수
수열	2	1	2	3	4	2	1

 (2-1) 왼쪽 index 를 넘겨봄

Index	추가	0	1	2	3	추가	4	추가 수
수열	2	1	2	3	4	1	2	2

 이후는... 직접 해보시길 권장하겠습니다... 절대 귀찮아서 건너 뛰는건 아닙니다.

(1) 코드 7~8

 'dp[i][j] : i,j 를 양 끝으로 하는 펠린드롬을 만드는 데 추가되는 최소 개수' 라고 설정했습니다.

 i=j 일 때 dp[i][j] = 0 이고, 구하고자 하는 답은 dp[0][N-1] 이겠죠?

(2) 코드 10~21

 각 탐색에서 과정(0)의 생각에 따라

    1. 탐색하는 양쪽 수가 같은경우

    2. 탐색하는 양쪽 수가 다른경우 

 를 생각 해주서 dp 값을 채우는 함수를 구현하였습니다.