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

Siver III

# 1463 가장 긴 증가하는 부분 수열

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

1463번: 1로 만들기

 

풀이

N = int(input())
li = list(range(N+1))
dp = [0 for i in range(N+3)]
dp[2] = 1
dp[3] = 1

for i in range(4, N+1):
    if i%3 == 0 and i%2 == 0:
        dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1
    elif i%3 == 0:
        dp[i] = min(dp[i//3], dp[i-1]) + 1
    elif i%2 == 0:
        dp[i] = min(dp[i//2], dp[i-1]) + 1
    else:
        dp[i] = dp[i-1] + 1

print(dp[-3])

 

후기

• i의 2 또는 3으로 나눈 약수 값이 i값을 구할 때 직접적인 영향을 준다. 따라서 동적 계획법으로 풀이하는 것이 좋다.
  
  
• 동적계획법을 사용할 때 dp라는 저장 공간 리스트를 만들어서 메모이제이션을 할 수 있도록 하자.
  
  
• 메모이제이션 된 값을 통해 i가 커질 때의 값을 빠르게 연산할 수 있다.