백준-1463-1로 만들기

문제

1로 만들기

풀이

1. 문제조건 해석

   입력 수에서 시작해서 1로 가는 연산 횟수 최솟값 구하는 문제

2. 알고리즘

   • dp로 풀 수 있다.
     • dp[i] : i까지 접근하는 연산 횟수의 최솟값
     • 한칸씩 이동하는 경우는 3번 연속해서 일어날 수 없다.
   • BFS로도 해결할 수 있다.

3. 코드

    ### DP로 해결하는 방법
    from collections import defaultdict
   
    n = int(input())
    # dp[i] : i번 인덱스까지 연산 횟수의 최소값
    dp = defaultdict(lambda:10**5)
   
    def dfs(n, level, flag):
        global dp
        dp[n] = level
        if n == 1:
            return
        if n % 3 == 0 and dp[n//3] > level+1:
            dfs(n//3, level+1, 2)
        if n % 2 == 0 and dp[n//2] > level+1:
            dfs(n//2, level+1, 2)
        if flag and dp[n-1] > level+1:
            dfs(n-1, level+1, flag-1)
   
    dfs(n, level=0, flag=2)# 2번까지 한칸씩 움직일 수 있다.
    print(dp[1])
   

    ### BFS로 해결하는 방법
    from collections import deque
    n = int(input())
    # BFS로 풀어보자
    queue = deque([n])
    step = 0
    visited = {n:step}
    while queue:
        step += 1
        for _ in range(len(queue)):
            pos = queue.popleft()
            if pos == 1:
                visited[pos] = step-1
                queue = None
                break
            if not pos%3 and pos//3 not in visited:
                visited[pos//3] = step
                queue.append(pos//3)
            if not pos%2 and pos//2 not in visited:
                visited[pos//2] = step
                queue.append(pos//2)
            if pos>1 and pos-1 not in visited:
                visited[pos-1] = step
                queue.append(pos-1)
    print(visited[1])
   

4. 배운점

   • 메모리 초과가 많이 일어났다. 가능한 경우의 수 최대로 줄이는 최적화를 잘 생각해야 한다.