[DP / python] 백준 1793 : 타일링

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

1793번: 타일링

 

문제 해석

다이나믹 프로그래밍은 분할 정복의 한 종류로, 복잡한 문제를 작은 문제들로 쪼개어 풀어내는 알고리즘이다. 여기서 핵심은, 잘게 쪼개진 문제 하나하나는 한 번만 푼다는 점이다.

 

다이나믹 프로그래밍을 적용시키기 위해서는 다음 두 가지 조건을 만족해야 한다.

조건 1. 큰 문제를 작은 문제로 나눌 수 있다.

조건 2. 작은 문제에서 구한 정답을 큰 문제에 적용할 수 있다.

 

해당 문제에서는 타일을 연속적으로 배치한 길이가 0, 1, 2와 같이 계속 쌓다가 어느 순간 길이가 n-2, n-1, n으로 되는 과정에서 타일 배치의 경우의 수를 찾아내는 방식이므로 타일을 쌓는 '패턴'이 존재할 것임을 예상할 수 있다. 패턴을 구한다면 모든 케이스를 해봐야 하는 것이 아니라 단위 패턴을 찾으면 되는 문제이니 큰 문제를 작게 쪼개는 것과 같아 DP를 적용하기 위한 조건1을 만족한다.

 

타일의 크기가 2x1과 2x2로 고정되어 있으므로 그 배치 형태 또한 반복될 것이므로 임의의 길이 n까지 이미 배치된 타일을 가정하여 점화식을 세울 수 있을 것이다. 또한 이는 그 길이가 어떻게 변하든 적용될 수 있으므로 DP를 적용하기 위한 조건2를 만족한다.

 

추가적으로, 이 문제는 입력의 양이 주어지지 않으므로 try/except로 묶어주어야 한다. (EOF)

 

풀이 코드

 

첫 번째 시도

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dp(n):
    global li
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 3
    if li[n] != 0:
        return li[n]
    li[n] = dp(n - 1) + 2*dp(n - 2)
    return li[n]

while True:
    try:
        n = int(input())
        li = [0] * (n+1)
        print(dp(n))
    except EOFError:
        break

결과: 실패

이유: EOFError를 지워야 한다. EOFError 외에도 다른 예외가 발생하나보다...

 

두 번째 시도

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dp(n):
    global li
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 3
    if li[n] != 0:
        return li[n]
    li[n] = dp(n - 1) + 2*dp(n - 2)
    return li[n]


while True:
    try:
        n = int(input())
        li = [0] * (n+1)
        print(dp(n))
    except: # 수정
        break

결과: 성공