1로 만들기

문제

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

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

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

입력

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

첫번째 풀이

X = int(input())
counter = 0

while X > 1:
    if X%3==0:
        X = X//3
        counter+=1
    elif X%2==0:
        X = X//2
        counter+=1
    else:
        X-=1
        counter+=1

print(counter)

10을 입력할때 2로 나누는것보다 1을 빼고하는것이 더 적어 틀리게된다. 그렇다고 항상 -1을 먼저 할 수 없어 잘못된풀이이다.

두번째

n = int(input())
d = [0]*1000001   # 최대숫자만큼 0으로 배열을 채운다.
d[1]=0
d[2]=1      # 미리 알고있는 값을 채우고,
d[3]=1      # 값을 호출하면 바로나올수 있게하여
d[4]=2      # 연산시간을 단축

for i in range(5, n+1):
    d[i] = d[i-1] + 1  # i-1 의 값 계산, 아래에서 %3이나 %2 가작으면 대체
    if i%3==0:
        d[i] = min(d[i], d[i//3]+1)
    if i%2==0:  # elif 대신 if 사용
        d[i] = min(d[i], d[i//2]+1)

print(d[n])

백준 1463