코딩테스트 대비/BOJ
[Baekjoon/Python] 1463번: 1로 만들기 - 효과는 굉장했다!
bluetag_boy
2021. 11. 12. 04:35
반응형
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
알고리즘 분류
- 다이나믹 프로그래밍
SOLUTION
import sys
N = int(sys.stdin.readline())
dp = [0 for _ in range(N+1)]
for i in range(2, N+1):
dp[i] = dp[i-1] + 1 # 1을 빼는 경우 일 때
if i % 2 == 0 and dp[i] > dp[i//2] + 1: # 2로 나누어 떨어지면 2로 나눈 수 에서 횟수 + 1
dp[i] = dp[i//2] + 1
if i % 3 == 0 and dp[i] > dp[i//3] + 1: # 3으로 나누어 떨어지면 3으로 나눈 수 에서 횟수 + 1
dp[i] = dp[i//3] + 1
print(dp[N])