[EPPER/13회 7번]회문을 만들기 까지의 횟수(중-1)

 

재귀를 이용

#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]){
				//뒤쪽이 더 작음 
				answer++;
				arr[end-1] = arr[end] + arr[end-1];
				solution(arr,start,end-1);
			
			}else if(arr[start]<arr[end]){
				//앞쪽이 더 작음
				answer=answer+1;
				arr[start+1] = arr[start] + arr[start+1];
				solution(arr,start+1,end);
			
			}else{
			//둘이 같음
				solution(arr,start+1,end-1);
			}
		}
		
	  return answer;
}

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

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

    return 0;
}

 

재귀아닌 버전

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


/*

배열의 처음과 맨 끝부터 비교해서 같으면 -> 그 다음을 재비교 (재귀)
배열의 처음과 맨 끝부터 비교해서 다르면 -> 둘중 더 작은쪽이 그다음과 더해짐 -> 재비교 

*/
int solution(vector<int> arr, int n){
	int start=0;
	int end = n-1;
	int answer=0;
	
	for(int i=0;i<arr.size();i++){
		if(start>=end) break;
		
		if(arr[start]> arr[end]){
			arr[end-1]=arr[end]+arr[end-1];
			end--;
			answer++;
		}
		else if(arr[start]<arr[end]){
			arr[start+1] = arr[start] + arr[start+1];
			start++;
			answer++;
		}
		else{
			start++;
			end--;
		}
	}
	return answer;
}
int answer = 0;


int main(void) {
    int n, i;
	vector<int> arr;
    int start = 0;
    int end = n;
	int num;
	
    cin >> n;
    for (i = 0; i < n; i++) {
		cin >> num;
		arr.push_back(num);

    }
    end = n - 1;

	cout<<solution(arr,n);
	
    return 0;
}