[Python] 백준 알고리즘 #1463 1로 만들기

문제풀이

 

이번 문제도 dp를 이용하면 쉽게 풀린다. dp문제는 규칙을 찾고, 점화식을 먼저 구해준다.

 

n	0	1	2	3	4	5
dp[n]	0	0	1	1	dp[2]+1	dp[4]+1

n>=2 부터 2,3으로 나누었을 때, 나누어지는지에 대한 여부를 살펴보고, 조건문을 이용해서 dp값을 추가해준다. 

 

dp[n] 의 값은

i) 2,3으로 모두 나누어질때는, dp[n//2], dp[n//3], dp[n-1] 에서 가장 작은 값 + 1

ii) 2로 나누어 떨어지고 3으로 나누어 떨어지지 않을 때, dp[n//2], dp[n-1] 에서 더 작은 값 +1

iii) 2로 나누어 떨어지지 않고, 3으로 나누어 떨어질 때, dp[n//3], dp[n-1] 에서 더 작은 값 +1

iv) 2,3 모두 나누어 떨어지지 않을 때, dp[n-1]+1

 

소스코드

import sys

input = sys.stdin.readline

dp = [0,0,1,1]

n = int(input())

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

print(dp[n])

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기