백준) 1695번: 팰린드롬 만들기 in C

Made with Stable Diffusion

Problem

1695번: 팰린드롬 만들기

Solution

 

Dynamic Programming, 즉 더 작은 문제로 쪼개서 푸는 문제이다.

DP의 경우, 어떤 문제를 DP를 적용해서 풀어야 하는지 파악을 할 수 있는 게 관건인 것 같다.

다양한 문제를 접해보면서 감을 익혀야겠다.

 

우선 Palindrome 수열의 내부에는 더 작은 Palindrome이 존재한다는 것에서 힌트를 얻을 수 있다.

 

예를 들어 1, 2, 3, 3, 2, 1 수열은 Palindrome이다. 따라서 Palindrome을 만들 때 필요한 수의 개수는 0이다.

가장자리에 있는 두 수 1을 빼면 2, 3, 3, 2 또 다른 Palindrome이고 여기에서도 필요한 수의 개수는 0이다.

마지막으로 다시 가장자리 두 수 2를 빼면 3, 3, 또 다른 Palindrome이 있다. 마찬가지로 필요한 수의 개수는 0이다.

이는 애초에 Palindrome일 때의 얘기이므로 Palindrome이 아닐 때도 보자.

 

위 문제의 예시로 나온 1, 2, 3, 4, 2의 경우,

일단 가장 바깥 두 수인 1, 2를 제외한 내부의 수열은 무시한다고 하자.

가장자리의 두 수 1, 2는 서로 다르므로 Palindrome이 아니다.

따라서 경우 중

1) 수열의 가장 왼쪽에 2를 추가를 하던지, (2, X, X, X, X, 2)

2) 가장 오른쪽에 1을 추가를 하면 (1, X, X, X, X, 1)

수열 내부(X)를 고려하지 않는 한 Palindrome이 된다. 이 때 우리는 Palindrome에 필요한 수의 개수가 최소 1 개임을 아는 것이다. (1 또는 2)

 

그리고 다시 내부를 본다.

앞에서 고려했던 두 가지 경우 중

1)의 경우 내부의 수열이 1, 2, 3, 4가 되고, (전체 수열: 2, 1, 2, 3, 4, 2)

2)의 경우 2, 3, 4, 2가 된다. (전체 수열: 1, 2, 3, 4, 2, 1)

 

우리는 당연히 두 경우 중 2번을 고를 때 Palindrome을 만들기 위해 필요한 수의 개수가 더 적을 것임을 안다.

1번은, 1, 2, 3, 4 뒤에 3, 2, 1 총 3개가 붙어야 Palindrome이지만

2번은 가운데에 3이나 4를 넣으면 Palindrome을 만들 수 있음을 알기 때문이다.

따라서 2번을 고른 뒤 다시 내부의 수열을 확인한다.

 

위의 과정을 수도코드로 작성하면 다음과 같다.

H부터 T까지의 최소 개수:
	H번째 수와 T번째 수가 같은 경우:
                H+1부터 T-1까지의 최소 개수 + 0
        
	다른 경우:
		H+1부터 T까지의 최소 개수 + 1
        	또는
       		H부터 T-1까지의 최소 개수 + 1
        	중 최소값

 

 

아래 코드는 알고리즘은 맞았지만 시간 초과가 떠서 오답인 코드이다.

#include <stdio.h>

int N, arr[5000];

int min(int a, int b){
	return (a < b)? a : b;
};

int DP_palin(int head, int tail){
	if(head == tail)
		return 0;

	if(arr[head] != arr[tail])
		return min(DP(head+1, tail) + 1, DP(head, tail-1) + 1);
	else
		return DP(head+1, tail-1);
};

int main(){
	int i;
	
	scanf("%d", &N);
	
	for(i=0;i<N;i++)
		scanf("%d", &arr[i]);
	
	printf("%d\n", DP(0, N-1));

	return 0;
}

즉 재귀함수로 풀지 말고 2차원 배열로 DP를 표현하고 풀이할 것을 요구한다.

 

Code

#include <stdio.h>

int N, arr[5000], DP[5000][5000] = {0,};

int min(int a, int b){
	return (a < b)? a : b;
};

int DP_palin(){
	int i, j, size = 1;
	
	for(i=0;i<N;i++){
		for(j=0;j+size<N;j++){
			if(arr[j] != arr[j+size])
				DP[j][j+size] = min(DP[j+1][j+size] + 1, DP[j][j+size-1] + 1);
			else
				DP[j][j+size] = DP[j+1][j+size-1];
		}
		size++;
	}
	
	return DP[0][N-1];
};

int main(){
	int i;
	
	scanf("%d", &N);
	
	for(i=0;i<N;i++)
		scanf("%d", &arr[i]);
	
	printf("%d\n", DP_palin());

	return 0;
}