Baekjoon 1463번 1로 만들기

문제

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

걸린 시간

00 : 17 : 50

풀이

Python3

from collections import deque

def bfs(N):
    q = deque()
    q.append([N, 0])
    visited = [0]*1000001
    while q:
        value, depth = q.popleft()
        depth += 1
        # 기저 사례
        if value == 1:
            break
        # 3가지 연산
        if value%3 == 0 and not visited[value//3]:
            q.append([value//3, depth])
            visited[value//3] = 1
        if value%2 == 0 and not visited[value//2]:
            q.append([value//2, depth])
            visited[value//2] = 1
        if value > 1 and not visited[value-1]:
            q.append([value-1, depth])
            visited[value-1] = 1
    return depth-1

N = int(input())
print(bfs(N))

입력받은 정수를 1로 만들기 위해 사용할 수 있는 연산이 3가지이고, 사용하는 연산의 최소값을 구해야 하므로 BFS 를 사용하여 풀이하였다.

다른 풀이

C++

#include <stdio.h>
#include <iostream>
#include <string.h> // memset
using namespace std;

#define INF 987654321

int N;
int cache[1000001];

int solve(int n){
    // 기저 사례
    if(n == 1)
        return 0;
    // 메모이제이션
    int& ret = cache[n];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = 1+solve(n-1);
    if(n%2 == 0)
        ret = min(ret, 1+solve(n/2));
    if(n%3 == 0)
        ret = min(ret, 1+solve(n/3));
    return ret;
}

int main(){
    scanf("%d", &N);
    memset(cache, -1, sizeof(cache));
    printf("%d\n", solve(N));
    return 0;
}

문제의 본래 의도인 dp 풀이이다. 제출하면 통과하긴 하지만 로컬에서는 환경의 문제인지 큰 수를 입력받게되면 오류가 발생하고 종료된다.

다른 방법으로 아래 첨부한 링크에 최소 코스트 재귀 알고리즘이 있는데 메모이제이션을 사용하지 않아도 뛰어난 성능을 보인다.

참고

• 최소 코스트 재귀 알고리즘