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

알고리즘 분류: 다이나믹 프로그래밍

 

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

1463번: 1로 만들기

 

내 풀이😊

# 정수 N 입력
n = int(input())

# DP 테이블 초기화
dp = [0] * (n + 1)

# 다이나믹 프로그래밍 - 보텀업
for i in range(2, n + 1):
    # 1 빼기 연산 수행
    dp[i] = dp[i - 1] + 1
    # 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    # 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[n])

 

 

 

백준 문제 풀이 깃허브 주소입니다 :)

https://github.com/Yiseull/baekjoon

GitHub - Yiseull/baekjoon