정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
10
3
(10->9->3->1)
이전에 풀었던 이코테 1로 만들기와 거의 흡사한 문제이다.
제목은 '1로 만들기'인데, top-down⬇ 방식으로 푸는 것보다 아예 1부터 시작하는 bottom-up⬆ 방식이 훨씬 수월하게 풀린다.
아래 엉성하게 그린 가지치기를 보자.
겹치는 수들이 많이 생겨 top-down⬇으로 하다가 처음에는 일단 계산을 하고, 앞에서 맞닥뜨렸던 수일 경우 그 수의 최소 연산 횟수를 불러오면 되지 않을까 하는 생각이 들게 된다. 💭
하지만 각각의 수가 나왔을때부터 1이 될 때까지의 과정을 일일이 관찰하기엔 꽤 많은 비용이 소요된다.
하나의 루트가 아니라 여러 가지 루트로 쪼개지니 각 루트로 현재까지의 연산 횟수를 계속해서 보내줘야 하고, 연산 결과 매번 새로운 수가 나오면 해당 수 또한 1이 될 때까지의 과정을 관찰해줘야 하기 때문이다. 딱 봐도 구현이 굉장히 짜증날 것 같은 예감이 든다...😵😖
그림을 보면 어쨌거나 우리는 1부터 X까지의 모든 수를 살펴봐야 한다는 것을 알 수 있다. 왜냐하면 계속해서 1로 빼기만 하는 경우도 존재하기 때문이다. 여기서 🍀HINT🍀를 얻어서, 거꾸로 1부터 최소 연산 횟수를 구하도록 한다.
✅구한 최소 연산 횟수는 항상 최소임을 보장한다.
어떤 수 N에서 연산 가능한 모든 경우에서, 각각의 연산 결과 M은 무조건 N보다 작고, M을 1로 만드는 최소 연산 횟수는 이미 앞에서 결정되었기 때문에,
(M들의 최소 연산 횟수들 중 가장 작은 값+1)
➡ N을 1로 만드는 최소 연산 횟수
d
리스트에 최소 연산 횟수를 저장한다. 진한 값(더 작은 값)이 해당 인덱스에 저장된다.
d[1]
: 시작점이니 0
d[2]
: 2에서 1을 빼면 1 ➡ d[1]+1(1) / 2에서 2를 나누면 1 ➡ d[1]+1(1)
d[3]
: 3에서 1을 빼면 2 ➡ d[2]+1(2) / 3에서 3을 나누면 1 ➡ d[1]+1(1)
d[4]
: 4에서 1을 빼면 3 ➡ d[3]+1(2) / 4에서 2를 나누면 2 ➡ d[2]+1(2)
.
.
.
d[9]
: 9에서 1을 빼면 8 ➡ d[8]+1(3) / 9에서 3을 나누면 3 ➡ d[3]+1(2)
d[10]
: 10에서 1을 빼면 9 ➡ d[9]+1(3) / 10에서 2를 나누면 5 ➡ d[5]+1(4)
def toone(x):
d[1]=0
for i in range(2,x+1):
#1 빼기
d[i]=d[i-1]+1
#2 나누기
if i%2==0:
d[i]=min(d[i], d[i//2]+1)
#3 나누기
if i%3==0:
d[i]=min(d[i], d[i//3]+1)
return d[x]
n=int(input())
d=[0]*(n+1)
print(toone(n))