[백준/BOJ] #2718 타일 채우기.python(파이썬)

문제 링크 / 출처

https://www.acmicpc.net/problem/2718

2718번: 타일 채우기

 

문제 요약

2*1, 1*2 크기의 블럭을 사용해 주어진 4*N크기의 공간을 빈틈없이 채우는 방법의 수를 구하는 문제

[제약사항]
- T <= 1000, T는 자연수
- N은 자연수
- N은 전체 경우의 수가 2,147,483,647이하이도록 주어짐

 

풀이

2*N 공간에 블럭을 채우는 문제의 확장버전이다. 

N을 a+b = N이고, 1 <= a,b < N 인 모든 경우로 분할하여 각각의 경우의 수를 구하고 더하는 방법을 사용해 풀이했다. 

3이상의 임의의 N에 대하여 두 개의 자연수로 분할되지 않는 경우의 수는 N이 홀수일 때 2가지, N이짝수일 때 3가지이므로,

이를 고려하여 분할되지 않는 경우를 가지수를 저장하는 리스트(cnt)와 임의의 수에 대하여 모든 경우를 저장하는 리스트(dp)를 사용하여 계산해주었다. 

 

코드

# 타일 채우기
T = int(input())

# 초기상태 저장
dp = [1, 1, 5]
cnt = [0, 1, 4]

for _ in range(T):
    N = int(input())

    # 이미 계산해둔 값이면 바로 출력하고 넘어감
    if N < len(dp):
        print(dp[N])
        continue

    idx = len(dp)

    # 계산해둔 범위를 넘을 경우 계산해 줌
    while N >= idx:
        cnt.append(2 if idx % 2 else 3)
        temp = 0

        for i in range(idx):
            temp += dp[i] * cnt[-i-1]

        dp.append(temp)
        idx += 1

    # 계산한 값 출력
    print(dp[N])