[백준-파이썬] 13301: 타일 장식물

백준 문제 보러가기!

코드

N = int(input())
tiles = [0]*81
tiles[1] = 1
tiles[2] = 1

def fibo(n):
    if tiles[n]!=0:
        return tiles[n]

    tiles[n] = fibo(n-1)+fibo(n-2)
    return tiles[n]

if N == 1:
    print(4)
else:
    print(fibo(N)*4 + fibo(N-1)*2)

설명

• 타일 한 변의 길이는 피보나치 수열로 증가한다.
• 타일 각 변의 길이를 한번 구하면, 그것을 tiles에 저장한다.
• 타일의 개수 N(1 ≤ N ≤ 80)라는 조건이 있어서 tiles = [0] * 81로 했다.
• 타일의 변 길이가 필요하고, 그것을 이미 구한 적이 있다면 return tiles[n]으로 꺼내온다!
• 즉 메모이제이션 방법이다 !

헷갈렸던 점

채점사이트에서 100%까지 가서 계속 틀렸다고 했다.
그 이유는 N = 1일 때를 고려하지 않아서 그런 것이었다.

if N == 1:
    print(4)

부분을 넣으니까 잘 되었다!
만약 이 부분이 없었다면, N이 1일 때, print(fibo(1)*4 +fibo(0)*2)을 구하려고 할 것이다.
fibo(0)은 tiles[0]이 0이므로 tiles[0]=fibo(-1) +fibo(-2)가 된다.
fibo(-1)을 구하려고 하면, tiles[-1]을 본다. 인덱스 값이 마이너스이면, 뒤에서부터 인덱스를 세는 것이다. 그런 식으로 계속 값이 구해지니까, 값이 나오긴 해도 이상한 결과가 나왔던 것이다.