[백준/python] 1463번 : 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

정답

import sys
from collections import defaultdict

number = int(sys.stdin.readline())
count = defaultdict(lambda : 999999)
count[1], count[2], count[3] = 0, 1, 1

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

print(count[number])

---

입력받은 숫자 number에서 1로 내려가는 것이 아닌

1에서 number로 올라가는 방식으로 풀이했다.

 

defaultdict를 이용하여 가장 큰 수로 초기화해놓고

2와 3은 무조건 1번이므로 1로 초기화한다.

 

값을 모르는 4부터 number까지 확인하기 위해 범위를 4, number+1로 지정하여 반복한다.

3으로 나누어 떨어지는 경우와 2로 나누어 떨어지는 경우를 고려하여

3으로 나눈 값, 2로 나눈 값, 1을 뺀 값의 count 중 가장 작은 값에서 1을 더하여 count에 저장한다.

 

마지막으로 number에 도달하기 까지 횟수인 count[number]을 출력한다.