[BOJ 1436] 1로 만들기

1) 문제 링크

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

2) 접근

X와 X/2, X/2, X-1의 관계를 줬다는 점에서 DP 문제라는 생각이 들었다. 이후 연산 횟수의 최솟값을 기록하는 cnt 배열을 만들고, 최솟값을 갱신해 나가는 방식으로 코드를 짰다. 시간복잡도는 O(n)이다.

3) 풀이

#include <iostream>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;

    cin >> N;

    int cnt[N+1] = {0, };

    cnt[1] = 0;
    cnt[2] = cnt[3] = 1;

    for(int i=2; i<N; ++i){
        if(i*3 <= N && (!cnt[i*3] || cnt[i*3] > cnt[i] + 1)) { cnt[i*3] = cnt[i] + 1; }
        if(i*2 <= N && (!cnt[i*2] || cnt[i*2] > cnt[i] + 1)) { cnt[i*2] = cnt[i] + 1; }
        if(i+1 <= N && (!cnt[i+1] || cnt[i+1] > cnt[i] + 1)) { cnt[i+1] = cnt[i] + 1; }
    }

    cout << cnt[N];

    return 0;
}

4) 피드백

아직 종만북을 제대로 안 보긴 했지만… 애초에 DP는 for로 돌리는 것 외에도 재귀함수를 이용하는 방법도 있다. 그리고, 무작정 돌리는 것보다 재귀로 돌리는 게 실행 시간을 대폭 감소시킬 수도 있다. 메모이제이션까지 더한다면 더더욱.

30124463번 코드는 이 문제를 재귀함수를 이용하여 해결한 예이다. 일단 2 이상의 자연수면 나누기 연산을 이용해야만 최적해가 도출된다는 것을 이용해 삼항 연산자에 2가지 case를 담았고, 나머지 연산을 사용함으로써 배수 여부에 관계없이 재귀 가능하게 했다는 것이 특징이다. 이런 거 보고 배워야겠당.