[백준]13699-점화식

문제바로가기

n = int(input())

if n == 0 or n == 1:
    print(1)
    exit()
elif n == 2:
    print(2)
    exit()
    
t = [0]*(n+1)
t[0]=t[1]=1
t[2] = 2

if n>=3:
    for i in range(3,n+1):
        if i%2 == 0:
            for j in range(i//2):
                t[i] += t[j]*t[i-(j+1)]*2
        else:
            for j in range((i-1)//2):
                t[i] += t[j]*t[i-(j+1)]*2

            t[i]+=t[(i-1)//2]*t[(i-1)//2] 
print(t[n])

처음에 99%에서 런타임에러(indexerror)가 났는데 그 이유가 n이 2 이하인 경우 예외처리를 해주지 않았기 때문이다. 조금만 생각해보면 t가 n+1개인데.. 어떻게 그냥 t[2] 라고 쓸 생각을 했지? 코딩은 역시 디테일이다.
다 풀고나서 다른 풀이나 효율적인 방법이 있는지 찾아보는데 추가적으로 값이 커지는 것을 방지해 mod연산을 적용하면 좋다고 한다.
t[i]+=(t[j]...)%1000000007