백준 1463번 - 파이썬 : dp 문제에서 런타임에러 원인

 

1463번: 1로 만들기

처음에 문제를 풀고 런타임 에러가 났다. 그 이유는 입력조건이 1보다 크거나 같은!!! 수에서 100만 보다 작은 수가 입력 인데

1보다 큰 것으로 잘못보고 지나쳤다. 1을 입력하니 에러가 났다.

이전 코드

n = int(input())

d = [0] * (n+2)

d[2] = 1
d[3] = 1

if n == 2 or n == 3:
    print(d[n])
    exit(0)
else:
    for i in range(4, n + 1):
        a = 1000000
        b = 1000000
        c = 1000000
        if i % 2 == 0:
            a = d[i // 2] + 1
        if i % 3 == 0:
            b = d[i // 3] + 1       
        c = d[i - 1] + 1
        d[i] = min(a, b, c)
print(d[n])

나는 위와 같은 bottom up 방식으로 for문을 이용해서 문제를 풀었다. 이 때는 항상 초반 값을 미리 할당해주는 특징을 가지고 있는데, 나는 여기서 1을 입력했을 때, 있지도않은 d[3] 값을 할당해주고 있으니 에러가 날 수 밖에,,

문제는 꼼꼼히 읽고, for문 시작 범위는 웬만하면 크게 잡자. 초반 값을 미리 여러 개 잡을 필요 없을 때는 그렇게 하지 말자.

따라서 아래와 같이 고쳤다! 

성공 코드

n = int(input())

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

if n <= 1:
    print(d[n])
    exit(0)
else:
    for i in range(2, n + 1):
        a = 1000000
        b = 1000000
        c = 1000000
        if i % 2 == 0:
            a = d[i // 2] + 1
        if i % 3 == 0:
            b = d[i // 3] + 1       
        c = d[i - 1] + 1
        d[i] = min(a, b, c)
print(d[n])