백준 1463번 파이썬 _ 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제유형 : DP

문제풀이 :

• 최적부분구조와 중복되는 부분문제를 만족하므로 DP(다이나믹 프로그래밍)으로 풀어야하는 문제이다.
• 현재의 최적의 해 = 2로 나누었을때 최적의해, 3으로 나누었을때 최적의해 중 작은값 + 1 ( 물론 나누어 떨어질때만 나눌수있음)

정답코드:

import sys
input = sys.stdin.readline

n = int(input())

dp = [1] * (n+1) # 숫자랑 인덱스 일치시키기 위해서 0은 안쓰는걸로

if n==1:    # 1이면 0이므로 출력하고 종료 
    print(0)
    exit()

for i in range(4,n+1):   # 2,3은 1이니까 4부터 반복문 
    if i%2==0 and i%3==0:  # 2,3모두 나누어떨어지는 숫자면 
        dp[i] = min(dp[i//2], dp[i//3]) +1
    elif i%2==0:				# 2로만 나뉘는 숫자면 
        dp[i] = min(dp[i//2], dp[i-1])+1
    elif i%3==0:				# 3으로만 나뉘는 숫자면 
        dp[i] = min(dp[i//3], dp[i-1])+1
    else:						# 2,3어떤걸로도 안나뉘는 애면
        dp[i] = dp[i-1]+1

print(dp[n])

더 좋은 코드 : 

이렇게하면 더 간단하게 위와 동일한 코드를 작성할수 있다.

3가지경우에 대해서, 해당하는경우를 모두 체크하되 가장작은값으로 갱신됨

for i in range(2, n+1):
	d[i] = d[i-1]+1
    
    if i%2==0:
    	d[i]=min(d[i], d[i//2]+1)
    if i%3==0:
    	d]i]=min(d[i], d[i//3]+1)