백준 1463: 1로 만들기 - 파이썬

1로 만들기  성공

1463번: 1로 만들기

문제

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

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

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

입력

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

출력

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

 

내 코드

 

n=int(input())
cnt=[0]*(n+1) #cnt[n]으로 접근하기 편하게 n+1개로 세팅.

for i in range(2, n+1): #1은 이미 1이므로 2부터 시작.
    cnt[i]=cnt[i-1]+1 #기본적으로 나보다 하나 작은놈보다 +1으로 세팅(->1 뺐을때의 경우)

    if i%2==0: #2로 나눠지는 놈이면,
        cnt[i]=min(cnt[i],cnt[i//2]+1) #위에꺼랑 나를 2로 나눈놈+1 중 작은놈 선택

    if i%3==0: #3으로 나눠지는 놈이면,
        cnt[i]=min(cnt[i],cnt[i//3]+1) #위에꺼랑 나를 3으로 나눈놈+1 중 작은놈 선택
    
print(cnt[n]) #n이 1이 되는 최소횟수는 cnt[n]에 저장되어 있다.

 

풀이 및 접근)

- 동적 프로그래밍의 아이디어가 필요하다. 점화식을 도출해 내는 것이 중요하다.

- 약간 실수한 부분은, if문 두개를 if~elif로 작성하는 것이 아니라 두개의 if문으로 작성해야 한다. 2와 3의 공배수인 경우, if~elif를 하게되면 2로 나누는 케이스 혹은 3으로 나누는 케이스 한가지만 실행하게 된다. 이렇게 하면 안되고, 2와 3모두 실행하는데 그 중 최소의 값으로 값을 넣어야 한다.

- 또 에러가 났던 부분은, cnt[i//2]와 cnt[i//3]의 부분에서, 당연히 if문 안에서 이루어져서 i가 2의 배수나 3의 배수가 보장되어 cnt[i/2], cnt[i/3]으로 해도 무방할 줄 알았다. 하지만 돌리려니 TypeError: list indices must be integers or slices, not float 가 떴다. 이를 주의하자.