백준 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 값을 채우는 함수를 구현하였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 5005;
	int N;
	int arr[MAX];
	// dp[i][j] : i,j 를 양 끝으로 하는 펠린드롬 만드는 데 필요한 최소 개수
	int dp[MAX][MAX];
	int palin(int s, int e) {
	if (s >= e) return 0;
	int& ret = dp[s][e];
	if (ret != -1) return ret;
	ret = 0; // 초기 0으로 생각
	// arr[s] = arr[e] 인 경우 그냥 안쪽으로 탐색
	if (arr[s] == arr[e]) ret += palin(s + 1, e - 1);
	// arr[s]!=arr[e] 인 경우 한쪽 맞춰주고(+1) 넘겨보는 것 중 작은거.
	else ret += 1 + min(palin(s + 1, e), palin(s, e - 1));
	return ret;
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> arr[i];
	memset(dp, -1, sizeof(dp));
	cout << palin(0, N - 1) << '\n';
	return 0;
	}

view raw BOJ 1695.cpp hosted with ❤ by GitHub