1463번-1로 만들기

문제

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

1463번: 1로 만들기

---

접근방법

1) 접근 사고

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이런 형식으로 문제에서 재귀함수로 구현하면 구현하기 쉽게 힌트를 준다.

이런 방식을 완전탐색으로 풀려고 접근하여 각각의 경우에서 수 많개의 경우의 수로 분할 되기 때문에 시간초과가 나므로 시간복잡도를 줄여야 하는 문제임을 알 수 있다.

 

2) 시간 복잡도

memorization 기법을 사용한 DP로 접근

 

3) 배운 점

memorization을 활용해서 탑다운 방식의 알고리즘을 구현해 보았다.

 

4) PS

문제를 잘못 이해해서 1로 주어지는 경우도 1번 연산해주는거라 생각해서 계속 오답을 맞았다.

문제를 정확히 읽는 습관을 가지자..

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e6 + 1;
int cache[MAX];
 
int search(int value)
{
    int &ret = cache[value];
 
    if (ret != -1)
        return ret;
 
    if (value <= 1)
        return ret;
 
    int tmp = 987654321;
 
    if (value % 3 == 0)
        tmp = min(tmp, search(value / 3));
    if (value % 2 == 0)
        tmp = min(tmp, search(value/ 2));
    tmp = min(tmp, search(value - 1));
 
    return ret = tmp + 1;
}
 
int main(void)
{
    int n;
    cin >> n;
    memset(cache, -1, sizeof(cache));
    cache[0] = 0;
    cache[1] = 0;
 
    cout << search(n) << "\n";
    return 0;
}