문제 : https://www.acmicpc.net/problem/2133

3x12 벽을 타일로 채운 예시

• 사실 구현자체는 어렵지 않지만, 타일을 채우는 방법이 독특해서 따로 정리하기로 했다. 아마 문제 아래 주어지는 힌트가 없었다면 한참 헤맸을 것 같다.

풀이

• 타일을 배치하는 경우의 수는 다음과 같다.

• 즉 i번째 칸에서 배치할 수 있는 경우의 수는 아래와 같이 표현할 수 있다.

(i-2칸에서 경우의 수 * 3) + (i-4칸에서 경우의 수 * 2) + (i-6칸에서 경우의 수 * 2) + …

• 또한 벽의 가로 길이가 짝수인 경우에만 배치가 가능하므로, 문제에서 주어진 N이 홀수인 경우 답은 무조건 0이 된다.

코드

정직하게 for문 돌기

if __name__ == "__main__":
    N = int(input())
    dy = [0] * (N+1)
    dy[0] = 1
    for i in range(2, N+1):
        dy[i] = dy[i-2] * 3
        for j in range(i-4, -1, -2):
            dy[i] += dy[j] * 2
    dy[0]= 0
    print(dy[N])

i가 홀수일 때는 0임을 감안하고 슬라이싱 이용하기

if __name__ == "__main__":
    N = int(input())
    dy = [0] * (N+2)
    dy[0] = 1
    dy[2] = 3
    for i in range(4, N+1, 2):
        dy[i] = dy[i-2] * 3 + sum(dy[:i-2]) * 2
    dy[0] = 0
    print(dy[N])

백준 기준으로, 두방법은 동일한 시간이 걸린다.