1463 1로 만들기

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

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

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

 

키워드 : dp[i]라는 특정한 시점에서 생각했다. dp[i]를 i의 숫자일 때 연산의 최소값이라 두고 

i//3 , i//2 , i-1 중 최소값(min)에 +1한 값이라고 생각했다.

그래서 3으로 나누어 떨어질 때 , 2로 나누어 떨어질 때, 1을 뺄 때 3가지로 경우를 두고 풀었다.

 

import sys
#N입력받기
N=int(sys.stdin.readline())
#dp테이블 초기화
dp=[ 0 for i in range(2*N)]
dp[1]=0
dp[2]=1
for i in range(3,N+1):
    if i % 3==0 and i%2==0:
        dp[i]= 1+ min(dp[int(i/3)] , dp[int(i / 2)] , dp[i-1])
    elif i % 3 == 0:
        dp[i] = 1 + min(dp[int(i/3)], dp[i - 1])
    elif i % 2 == 0:
        dp[i] = 1 + min(dp[int(i /2)], dp[i - 1])
    elif i%3!=0 and i%2!=0:
        dp[i]=dp[i-1]+1

print(dp[N])

 

하지만 계속 런타임 에러가 떴었다.

 

풀이 

사실 위 풀이에서도 대입 부분만 없애면 정답이다.

더 최적화 시키는 코드로는 우선 dp[i-1]에 1을 더해서 1을 뺀경우로 먼저 만든 후,

3이나 2로 나누어 떨어지는 경우에 최소값을 비교해서 메모이제이션을 활용하면 된다.

 

대입했을 때 왜 런타임에러가 뜨는지 모르겠다 ; 

아니면 그냥 4개 넣어놓고 append로 하는것도 괜찮겠다.

 

#N입력받기
N=int(input())
#dp테이블 초기화
dp=[0]*(N+1)
for i in range(3,N+1):
   dp[i]=dp[i-1]+1
   if i % 3 == 0:
     dp[i] = min(dp[i//3]+1, dp[i])
   if i % 2 == 0:
     dp[i] =min(dp[i//2]+1, dp[i])
print(dp[N])