카테고리 없음

[Do it! 알고리즘 코딩테스트 with Python] 동적 계획법 예제 - 정수를 1로 만들기

ssungni 2024. 3. 23. 00:45

문제

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

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

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

 

입력 출력
10 3

1, 10 - 1 = 9

2. 9 / 3 = 3

3. 3 / 3 = 1

 

해결 과정

1) 각각의 경우에 따른 연산횟수 구하는 방법 도출하기 => 예제를 똑바로 쳐다보기

2) 조건문 만들어주기

D[i] = D[i - 1] + 1
if(i % 2 == 0) D[i] = min(D[i], D[i / 2] + 1)
if(i % 3 == 0) D[i] = min(D[i], D[i / 3] + 1)

 

3) 점화식 이용해서 DP 테이블 채우기

이렇게 하면 런타임 에러 뜨더라...

N = int(input())

D = [0] * (N+1)
D[1] = 0

for i in range(2, N+1):
    D[i] = D[i-1] + 1
    if (i % 2 == 0): 
        D[i] = min(D[i], D[i//2] + 1) 
    elif (i % 3 == 0): 
        D[i] = min(D[i], D[i//3] + 1) 

print(D[N])

 

정답

n = int(input())

d = [0] * 1000001

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

print(d[n])

 

여기서 d = [0] * 1000001로 수정했다고 런타임 에러가 안 나는 이유는 무엇일까?

오늘도 넌 역시 똑똑하구나...ㅠㅠ