[Baekjoon] 1463번 : 1로 만들기

실버 3

1463번: 1로 만들기

 

문제 풀이

세가지 경우에 대해 계산하고 최소값으로 보텀업하면 되는 문제

3으로 예를 들면

1) 1을 빼기 -> 2회 : 빼기 연산 1회 + 2를 1로 만드는 최소 연산횟수(1)

2) 2로 나누어 떨어지면 2로 나누기 -> 불가 (1e6)

3) 3으로 나누어 떨어지면 3으로 나누기 -> 1회 :  나누기 연산 1회

-> 이 세가지 경우 중 최소 값은 1회이다.

 

이를 코드로 나타내면 다음과 같다.

1) minus = dp[n-1] + 1
2) divide_3 = dp[n//3] + 1 (if n%3 == 0)
3) divide_2 = dp[n//2] + 1 (if n%2 == 0)
-> dp[n] = min(minus, divide_3, divide_2)

 

코드

n = int(input())

min_list = [0] * (n + 1)

for i in range(2, n+1):
    minus, divide_3, divide_2 = 1e6 + 1, 1e6 + 1, 1e6 + 1
    minus = min_list[i-1] + 1
    if i % 3 == 0:
        divide_3 = min_list[i//3] + 1
    if i % 2 == 0:
        divide_2 = min_list[i//2] + 1

    min_list[i] = min(minus, divide_3, divide_2)

print(min_list[n])