[기출 중] Palindrome 만드는 횟수 구하기

[문제]

Palindrome(회문)은 앞으로 읽으나 뒤로 읽으나 똑같은 배열을 의미한다. 예를 들어, 123321과 같은 배열은 회문이다. 회문이 아닌 배열은 인접한 요소들끼리 합쳐서 회문을 만들려고 한다. 예를 들어, 12351은 회문이 아니지만, 2+3의 한번의 수정을 통해 1551인 회문을 만들 수 있다. 이렇게, 회문이 아닌 배열이 주어졌을 때 회문을 만들 수 있는 가장 적은 수정 횟수를 구하도록 해라.

 

[풀이]

맨 앞과 맨 뒤부터 시작해 비교해 나가면서 대칭이면 통과하고, 대칭이 아니면 더 작은 숫자인 쪽을 합쳐서(횟수 증가) 대칭인지를 다시 비교해 본다. 

 

[코드]

#include <iostream>
#include <stdlib.h>
using namespace std;

int answer = 0;

int solution(int* arr, int start, int end) {
	if(start >= end)
		return answer;
	else if(arr[start] == arr[end])
		return solution(arr, start+1, end-1);
	else{ //회문 수정 필요
		answer++;
		if(arr[start] <= arr[end]){
			arr[start+1] += arr[start];
			return solution(arr, start+1, end);
		}
		else{
			arr[end-1] += arr[end];
			return solution(arr, start, end-1);
		}
	}
}

int main(void) {
    int n, i;
	int arr[10];
    int start = 0;
    int end = 0;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> arr[i];
    }
    end = n - 1;

    cout << solution(arr, start, end);

    return 0;
}