1로 만들기 백준 1463번

백준 1463번 문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

inp = int(input())
count = 0
while True:
    if inp%3==1:
        count+=1
        inp-=1
    if inp%3==0:
        count+=1
        inp=inp//3
    if inp%2==0:
        count+=1
        inp=inp//2
    if inp==1:
        break
print(count)

일단 떠오르는대로 while문을 가지고 풀어 보았다. 테스트케이스는 통과했지만 당연히 시간초과로 풀리지 않았다.

그래도 설명을 하자면 그냥 무식하게 3으로 나누었을때 나머지가 1이라면 1을 빼고 3의 배수라면 3으로 나누고 2의 배수라면 2로 나누고…. 했는데 다시보니 코드가 엉터리인것도 있다. 아무래도 주어진 값에서 내려가기보다 1에서 올라가는 것이 빠르 겠다는 생각이 들었다. 문제 분류도 다이나믹프로그래밍 아닌가

n = int(input())
d = [0] * (n + 1)

for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
        
print(d[n])

1부터 n까지 올라갑니다. 다만 리스트의 시작은 0부터이니 계산하기 편하게 하기 위해서 n+1개의 리스트를 생산합시다. 이부분은 편한데로 하시면 될 것입니다. 범위는 2부터 n까지입니다.

리스트에다가는 한칸전에 값에서 1칸 더한 것을 가져옵시다. 어자피 나중에 비교할 것이기 때문에 의미는 없습니다. 만약에 i가 3배다. 그러면 몫의 값을 가진 열에다가 1을 더한 값일 것입니다. 무슨 말인가 하면

3의 경우 1로 만드는데 1번 걸립니다. 3으로 나누는 것이니 까요

9의 경우 3일때 경우의(1번) + 1 입니다.

2도 마찬가지고요