1463 1로 만들기

악! 이제 메모이제이션 어떻게 쓰는지 알겠어!

알겠다고!!!!

 

행복하다 진자...

 

전에는 디피...? 배열 만들어서 반복문으로 바텀업...? 이정도로 알고 있어서 힘들어했는데 이제 감이 잡힌다

 

1. 먼저 해당 문제를 재귀로 풀 수 있는지 고민해본다.

2. 재귀로 쉽게 풀린다싶으면 재귀로 구현

3. 시간초과나면 메모이제이션을 쓴다

 

이 문제도 처음에 보고 어떻게 푸나 싶었는데 재귀로 짜면 좋을 것 같아서 재귀로 짜고 시간초과 나서 메모이제이션 사용했다. 

 

 

위는 재귀 로직

 

아래는 메모이제이션 사용한 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 1000000009

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

#define MAXV 1000005

int cache[1000005];

int func(int x)
{
    int a = MAXV, b = MAXV, c = MAXV;

    if (x <= 1)
        return 0;

    if (cache[x] != -1)
        return cache[x];

    if (x % 3 == 0)
        a = func(x / 3);
    if (x % 2 == 0)
        b = func(x / 2);
    c = func(x - 1);

    return cache[x] = min({ a, b, c }) + 1;
}

int     main()
{
    int x;
    scanf("%d", &x);

    memset(cache, -1, sizeof(cache));

    printf("%d\n", func(x));

    return 0;
}

 

이 다음 든 생각이 그럼 재귀는 시간초과 나보고 메모이제이션을 사용하나 싶었는데 북님한테 시간복잡도 어떻게 구하는지 배워왔다.

 

재귀함수에서 자기자신을 호출하는 횟수가 3번이고 그 함수가 다시 3번 호출하니깐 3제곱 꼴로 커질테고

 

최악의 경우에 n -1번 연산하니 적당히 O(3 ^ n)라고 계산할 수 있다.

 

그래서 단순재귀는 n = 10 ~ 20정도만 사용할 수 있음.. 입력값 엄청 작구나