백준 1463. 1로 만들기

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

1463번: 1로 만들기

BFS 풀이(내풀이)

import sys
from collections import deque

def bfs(n):
    q = deque([n])
    while q:
        n = q.popleft()
        if n == 1:
            return arr[n]
        if n % 2 == 0 and not arr[n//2]:
                 arr[n//2] = arr[n] + 1
                 q.append(n//2)
        if n % 3 == 0 and not arr[n//3]:
                 arr[n//3] = arr[n] + 1
                 q.append(n//3)
        if not arr[n-1]:
                 arr[n-1] = arr[n] + 1
                 q.append(n-1)

n = int(sys.stdin.readline())
arr = [0] * (n+1)
print(bfs(n))

처음엔 arr범위를 100001이런식으로 했는데 그럴 필요가 없다...!

그리고 n의 범위도 유효한 범위가 되게 했었는데 필요없음!

하지만 원래 이문제는 DP를 이용해서 푸는 문제!

---

바텀업 풀이

n=int(input())
d=[0]*(n+1)  # 인덱스별 연산횟수 저장(1은 0 고정)
for i in range(2,n+1): # 2부터 n까지
    d[i]=d[i-1]+1 # 1을 빼는 연산 -> +1해줌
    if i%2==0: # 2의 배수일때 
        d[i]=min(d[i],d[i//2]+1)  # 2로 나눴을 때(2로나눈것 포함이므로 +1)의 연산횟수와 아무것도 안했을때의 연산횟수 중 작은거 저장
    if i%3==0: # 동일
        d[i]=min(d[i],d[i//3]+1)
print(d[x])  # 1까지 가는 최솟값만 저장하게 됨

---

탑다운 풀이(재귀)

x=int(input())
dp={1:0}
def rec(n):
    if n in dp.keys():
        return dp[n]
    if (n%3==0) and (n%2==0):
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)
    elif n%3==0:
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)
    elif n%2==0:
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)
    else:
        dp[n]=rec(n-1)+1
    return dp[n]
print(rec(x))

 

앞에서 구한 결과값을 저장하였다가 후에 사용하는 것!