[파이선] 백준 1793 - 타일링 (python)

목차

문제 : boj1793

 

 

필요 알고리즘

• 동적 계획법(DP), 큰 수
  
  • 기본적인 형태의 DP 문제이다. 다만 큰 수를 처리하는게 포함되어 파이썬 이외로 풀긴 좀 까다롭다.

 

 

풀이

  별 생각없이 자바로 풀고보니 출력이 어마무시한 수였다.. ㅋㅋㅋㅋ DP를 BigInteger로 푸는 맛없는 짓은 하기 싫었으니 파이썬으로 갈아탔다. 이하 자바로 풀었다가 출력보고 버린 코드 이다.

 

 

  파이썬으로 푼 맨 아래에 있는 코드에서 결국 핵심은 다음 한 줄 뿐이다.

dp[i] = 2*dp[i-2] + dp[i-1]

 

  dp[x]를 x번째 열까지 타일을 놓는 경우의 수라 하자. dp[5]의 경우 아래 그림처럼 dp[4]에 2x1 타일을 놓는 경우와, dp[3]에 1x2 타일 2개를 놓는 경우, dp[3]에 2x2 타일을 놓는 경우가 있을 것이다. 그래서 dp[i] = 2*dp[i-2] + dp[i-1] 을 각 열에 대해 순서대로 계산해주면 된다. 최종적으로 답은 dp[n]이다.

  

  주의할점은 특이하게 n이 0도 입력으로 들어올 수 있다는 점인데, 이것때문에 좀 헷갈렸다. '타일을 채우는 방법'이라 했으므로 0이라 타일을 하나도 못놓아 '0'이 답일 줄 알았는데 '1'이 답이었다. 이 부분은 충분히 맞왜틀 외칠만한 부분이라 생각되서 적어봤다.

 

  참고로 input = sys.stdin.readline 이 부분은 입력 좀 빠르게 받게 처리하는 부분이고, try - except 처리해둔 부분은 EOF인 경우 끝내는 부분과, 입력으로 '\n' 즉 개행문자만 들어오는 경우 ValueError가 뜨므로 그거 포함해서 아무튼 에러나면 끝내려고 한 부분이다.

 

 

코드 : github

import sys
input = sys.stdin.readline

def initDpArray():
    global dp
    dp = [0 for i in range(n+3)]
    dp[0] = 1
    dp[1] = 1
    dp[2] = 3

while 1:
    try:
        n = int(input())
        initDpArray()

        for i in range(3, n+1):
            dp[i] = 2*dp[i-2] + dp[i-1]
        print(dp[n])

    except:
        break