본문 바로가기
백준 알고리즘

파이썬) 백준 알고리즘 | 1463번 : 1로 만들기

by 코딩새내기_ 2022. 3. 4.

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

백준 1463 '1로 만들기' 문제입니다.

제가 처음 푸는 DP 문제인데 DP를 이해하지 못하다가 이 문제에서 처음으로 이해한 것 같습니다.

n마다 3으로 나누기, 2로 나누기, 1빼기 각각의 케이스를 시도하고 가장 작은 값을 취해주는 식으로 구현하였습니다.

import sys
input = sys.stdin.readline
n = int(input())
dp = [-1] * (n+1)
minValue = 99999999
for i in range(1, n+1):
    if i % 3 == 0:
        a = dp[i//3] + 1
    else:
        a = 999999
    if i % 2 == 0:
        b = dp[i//2] + 1
    else:
        b = 999999
    c = dp[i-1] + 1
    dp[i] = min(a, b, c)
print(dp[n])

 

댓글