1463번

1463 - 1로 만들기

1. 완전 탐색을 이용해서 풀기

재귀 함수를 이용해서 모든 케이스를 다 돌려보았다.

재귀를 돌리는 중에 지금 현재의 최소값보다 큰 값이 나오면 return 해주는 방식으로 속도를 조금 빠르게 했다.

#include<iostream>
using namespace std;
int ans = 987654321;
void go(int n, int cnt)
{
    if (cnt > ans)
    {
        return;
    }
    
    if (n == 1)
    {
        ans = cnt > ans ? ans : cnt;
        return;
    }
 
    if (n % 3 == 0)
    {
        go(n / 3,cnt+1);
    }
 
    if (n % 2 == 0)
    {
        go(n / 2,cnt+1);
    }
 
    go(n - 1,cnt+1);
 
    return;
 
}
int main()
{
    int N;
    cin >> N;
 
    go(N,0);
 
    cout << ans << endl;
 
    return 0;
}

2. BFS를 이용해서 풀기

어떤 연산을 이용해도 연산 횟수는 1이 증가하기 때문에, 가중치가 1인 그래프라고 볼 수 있다.

그리고 이때의 연산횟수의 최솟값을 구하는 것이기 때문에 BFS로 풀 수 있었다.

#include<iostream>
#include<queue>
using namespace std;
bool check[1000001];
int dist[1000001];
int main()
{
    int n;
    cin >> n;
 
    queue<int> q;
 
    q.push(n);
    check[n] = true;
    dist[n] = 0;
 
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
 
        if (x == 1)
        {
            cout << dist[x] << endl;
            break;
        }
 
 
        if (x % 3 == 0 && check[x / 3] == false)
        {
            int nx = x / 3;
            q.push(nx);
            check[nx] = true;
            dist[nx] = dist[x] + 1;
        }
        if (x % 2 == 0 && check[x / 2] == false)
        {
            int nx = x / 2;
            q.push(nx);
            check[nx] = true;
            dist[nx] = dist[x] + 1;
        }
        if (check[x - 1] == false)
        {
            int nx = x-1;
            q.push(nx);
            check[nx] = true;
            dist[nx] = dist[x] + 1;
        }
    }
 
 
    return 0;
}

3.DP를 이용해서 풀기

나는 보통 재귀로 DP를 많이 푼다. for문을 이용해서 푸는 방법도 있지만...

솔직히 DP랑 완전탐색이랑 똑같다.. 다만 memoization 이 있다는..

근데 위의 완전탐색 풀때는 n/3, n/2 , n-1 로 풀었는데

아래 코드는 그 순서로 풀면 오류가 났다 왜 그럴까...?

혹시 오류 아시는 분은 말씀 좀 해주세요...ㅠㅠ

################################################################

D[N]=go(N-1)+1을 맨 마지막 줄로 바꾸면 오류가 발생하는 거 생각해보기. 질문올리기

################################################################

<정답 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int D[1000001];
int go(int N)
{
    if (N == 1)
    {
        return 0;
    }
    if (D[N] != -1)
    {
        return D[N];
    }
 
    D[N] = go(N - 1) + 1;
 
    if (N % 3 == 0)
    {
        D[N] = min(D[N],go(N / 3) + 1);
    }
    if (N % 2 == 0)
    {
        D[N] = min(D[N],go(N / 2) + 1);
    }
 
    
 
    return D[N];
 
}
int main()
{
    int n;
    cin >> n;
 
    memset(D, -1, sizeof(D));
    
    cout << go(n) << endl;
 
    return 0;
}

<오류 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int D[1000001];
int go(int N)
{
    if (N == 1)
    {
        return 0;
    }
    if (D[N] != -1)
    {
        return D[N];
    }
    if (N % 3 == 0)
    {
        D[N] = go(N / 3) + 1;
    }
    if (N % 2 == 0)
    {
        D[N] = min(D[N],go(N / 2) + 1);
    }
    D[N] = min(D[N],go(N - 1) + 1);
    return D[N];
}
int main()
{
    int n;
    cin >> n;
    memset(D, -1, sizeof(D));
    cout << go(n) << endl;
    return 0;
}