[Python/백준] 2133 타일 채우기

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

2133번: 타일 채우기

<문제 해설>

다이나믹 프로그래밍 문제입니다. 규칙을 찾아서 점화식을 만들면 됩니다. 문제에서 중요한점은 N이 짝수일 경우에는 2x1,1x2타일로 절대 채울수 없기 때문에 0을 출력해야합니다. 점화식을 세우는 과정을 예시를 들어서 설명하겠습니다.

점화식을 구한 이후엔 dp배열을 만들어서 n들의 가짓수를 저장해줍니다. 그리고 저장한 값들을 통해서 원하는 값을 구합니다.

<예시>

본사진은 n이 8일때까지의 가짓수를 그린 사진입니다.

• n = 2 : 채우는 방식이 3가지가 있습니다.
• n = 4 : 채우는 방식 2가지가 더해집니다. 그리고 n-2인 가짓수에 3을 곱한 값인 9가지가 더해집니다.
• n = 6 : 채우는 방식이 다시 2가지가 더해집니다(n=6 바로 아래있는 타일을 뒤집으면 다른경우가 되니 +2).                             n-2의 가짓수에 3을 곱한 가짓수를 더해줍니다(2+3*3)*3.
• n = 8 : 여기서 점화식이 확실해 집니다. n = 6처럼 n-2인 가짓수에 3을 곱한 값을 더해줍니다(빨간색 화살표).                         n-4아래있는 값들에 2를 곱해서 더해줍니다(파란색 화살표). 그후 새로추가되는 2를 더해줍니다.

따라서 n의 가짓수는 (n-2 가짓수 * 3) + (n-4이하의 모든 가짓수 * 2) + 2가됩니다.

<코드>

N = int(input())

if N % 2 != 0:
    print(0)
else:
    N = N//2
    dp = [0]*(N+1)
    dp[1] = 3
    for i in range(2,N+1):
        dp[i] += dp[i-1]*3
        for j in range(i-2,0,-1):
            dp[i] += dp[j]*2
        dp[i] += 2
        
    print(dp[N])

<코드 설명>

N = int(input()) //N값을 정수형으로 받아옵니다.

if N % 2 != 0: //홀수인 경우 무조건 0이니 분기점을 만들어 줍니다.
    print(0)
else: //짝수인경우 계산합니다
    N = N//2 //홀수일 경우는 굳이 계산할 필요도 없고 시간, 공간을 아끼기위해 2로 나누어줍니다.
    dp = [0]*(N+1) //짝수값들을 저장할 배열입니다.
    dp[1] = 3 //초기 값을 지정해줍니다.
    for i in range(2,N+1): //2부터 원하는 값인 N까지 dp를 구해줍니다.
        dp[i] += dp[i-1]*3 //n-2가짓수에 3을 곱합니다.
        for j in range(i-2,0,-1): //n-4이하의 가짓수에 2를 곱합니다.
            dp[i] += dp[j]*2 
        dp[i] += 2 //새로추가되는 2를 더합니다
        
    print(dp[N]) //N값을 출력해 줍니다.