[백준 1463번] 파이썬 - 1로 만들기

백준 1463_1로 만들기

조건

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다
• 위 3개의 연산을 적절히 사용해서 1을 만들어 주자.

접근 방법

• 최소의 연산을 구하는 문제이다.
• 2 또는 3으로 나누어 떨어지지 않는 경우 무조건 1을 빼야한다.
• 이후는 2와 3으로 나누어주면 되는데 min을 통하여 빼주는 것과 나누어주는 것의 최소값을 구해준다.
• n=>1이 아닌 1 => n의 형식으로
• dp 인덱스 => 연산 값, dp의 값 => 연산 횟수로 이용해준다.

n = int(input())
dp = [0] * (n+1)

for i in range(2, n+1):
    # 나눠지지 않는다면 무조건 1씩 빼야하므로 연산횟수 +1
    dp[i] = dp[i-1] + 1
    # 나누는게 훨씬 이득이므로, 최소값을 통해 갱신해준다.
    # -1로 들어온값 vs 나눠준값 +1
    # n => 1이 아닌 1=> n을 만들어주기
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] +1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

• 아래는 bfs를 이용한 풀이

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
q = deque([1])
dp = [0] * (N+1)
while q:
    now = q.popleft()
    if now == N:
        print(dp[N])
        break
    for i in [now+1, now*2, now*3]:
        if i <= N and not dp[i]:
            dp[i] = dp[now] + 1
            q.append(i)