1463 1로 만들기 _python

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

1463번: 1로 만들기

 

시간 제한이 0.15초

일반인의 반응속도0.25초보다 짧다. 일반인의 반응속도보다 빠르게 맞춰야 하는 문제.

막무가내 접근하면 틀린다.

count = 0
N=int(input())
while N!=1:
    if not N%3:
        N //= 3
    elif not N%2:
        N //= 2
    else:
        N -= 1
    count += 1

이렇게하면 10에서 4가 나온다.

다른 방식으로 접근해야 하는데 결국 해결하지 못하고 다른 블로그를 봤다.

내가 해결하지 못한 이유는 시간제한이 0.15초에 입력이 10^6이라서 절대 모든 경우를 파악하는건 말이 안된다고 생각했다.

 

 

문제 접근

풀이를 보고 놀란게, dp를 활용해도 시간초과일줄 알았는데 dp를 활용하는게 맞았다.

dp를 활용해서 2부터 3가지경우를 다 파악해서 최소값을 저장해두면서 진행해야한다.

dp의 상향식을 사용해서 1을 뺐을때, 2로 나누었을때, 3으로 나누었을때 계산중 최소값을 구해가면서 2부터 N까지 진행한다.

 

 

코드

 

import sys
input = sys.stdin.readline

N= int(input())
count = 0
dp = [0]*(N+1)

#dp[2]부터 dp[N]까지 상향식 사용
for i in range(2,N+1):
    dp[i] = dp[i-1]+1
    # -1과 2로 나누는 것 중 최소값을 저장
    if not i%2: dp[i] = min(dp[i],dp[i//2]+1)
    # 위의 최소값과 3으로 나눈것중 최소값을 저장
    if not i%3: dp[i] = min(dp[i],dp[i//3]+1)
        
print(dp[N])