카테고리 없음
[Do it! 알고리즘 코딩테스트 with Python] 동적 계획법 예제 - 정수를 1로 만들기
ssungni
2024. 3. 23. 00:45
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 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로 수정했다고 런타임 에러가 안 나는 이유는 무엇일까?

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