백준) - 1로 만들기(재귀함수) / C++

문제 출저 입니다.

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

사고의 흐름

 

일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다.  모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다.

 

다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 

 

해결방법

#include<iostream>
 
using namespace std;
 
static int* answer = new int[0];
 
 
int solution(int n) {
 
    
    if (n == 1) return 0;
    if (answer[n] > 0) return answer[n];
 
    answer[n] = solution(n - 1) + 1;
 
    if (n % 2 == 0) {
        int tmp = solution(n / 2) + 1;
        if (answer[n] > tmp) answer[n] = tmp;
    }
    if (n % 3 == 0) {
        int tmp = solution(n / 3) + 1;
        if (answer[n] > tmp) answer[n] = tmp;
    }
    return answer[n];
 
}
 
int main() {
 
    int n;
    cout << "n값을 입력하세요" << endl;
    cin >> n;
    cout << endl;
    
    answer = new int[n + 1];
    cout << solution(n);
}

 

결과

 

 

느낀점

역시 많은 문제를 풀어봐야겠다. 많은 문제를 풀고 많은 풀이과정을 배워야겠다.