5255. [파이썬 SW 문제해결 최적화] 2일차 - 타일 붙이기

내가 이런 문제만 보면 머리가 나쁘다는 걸 느낀다. 이해하기가 힘들다.

일단 감각적으로 풀었는데 막상 답이 되자 당황했었다.

우선 쉽게 풀어보기 위해 재귀방법을 이용해 풀었었다. 그 뒤 동적계획법으로 리스트에 저장해서 [0]에서 [n]까지 올라가면서 구하는 방식으로 해결했다.

내가 당황했던 부분은 inputbox(n-3) + 2*inputbox(n-2) + inputbox(n-1) 수식에서 왜 (n-2)에 *3이 아닌 *2를 해야 하느냐 였다.

그림을 그리고 나서야 이해할 수 있었다. 2칸을 차지하는 부분 b(n-2)에서 ll, --, ㅁ 이렇게 각각 3개가 있는데 왜 *3이 아니고 *2인가?

이것은 1칸을 차지하는 부분 b(n-1) 에서 차지할 때 l 로 차지하는데 이것이 2칸을 차지하는 부분 b(n-2)의 ll과 중복되기 때문.

그래서 --과 ㅁ만 남아 *2를 한다.

import sys

sys.stdin = open("sample_input.txt", "r")

def inputbox(n):
    if n <= 3:
        return BoxResultList[n]

    for i in range(4,n+1):
        if BoxResultList[i] != -1: continue
        BoxResultList[i] = BoxResultList[i-1] + 2*BoxResultList[i-2] + BoxResultList[i-3]
    return BoxResultList[n]

    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 3
    elif n == 3:
        return 6
    else:
        return inputbox(n-3) + 2*inputbox(n-2) + inputbox(n-1)


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())
    BoxResultList = [-1] * (N+1)
    BoxResultList[0] = 0
    BoxResultList[1] = 1
    BoxResultList[2] = 3
    BoxResultList[3] = 6
    result = inputbox(N)
    # print(result)
    # print(BoxResultList)

    print("#{}".format(test_case),result)

    # ///////////////////////////////////////////////////////////////////////////////////