[백준] 11726 : 2xn 타일링

1006번 문제를 풀다가 막혀, 해설을 찾아보던 중 11726번의 응용버전이라는 글에 이것부터 풀어보기로 했다.

풀이과정은 다음과 같다.

11726번 문제풀이

 

이 문제의 핵심은 , 현재의 문제가 더 작은 문제들의 합으로 나뉘어진다는 것이다.

즉 , 전체 경우의 수 = 처음에 2x1 타일을 붙였을 때의 경우의 수 + 처음에 1x2 2개 타일을 붙였을 때의 경우의 수, 로 정의된다.

이는 전형적인 DP(Dynamic Programming)문제이다.

 

DP문제를 풀기위해서는 2가지 정의가 필요하다.

 

1. 점화식 ( 재귀식과 같이 자기 자신의 함수의 합으로 표현되는 식 )

f(n) = f(n-1) + f(n-2)로 정의된다.

이는 피보나치 수열 문제와 완전히 동일하게 된다.

 

2.기본 상태 정의하기 ( n=1일때와 n=2일 때 )

if (n=1) return 1 , if (n=2) return 2.

 

이를 바탕으로 코드를 구현하면 다음과 같다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6) # 파이썬 최대 재귀깊이 높이기

stdin = open('11726/sample_input.txt', 'rt') # 테스트할 때, 제출할 때는 주석처리 해주기

cnt_dict = {}
cnt_dict[1] = 1; cnt_dict[2] = 2

def find_cnt(n: int) -> int:
  """
  n: 가로넓이
  """
  if (n in cnt_dict.keys()): return cnt_dict[n]
  
  cnt_dict[n] = find_cnt(n - 1) + find_cnt(n - 2)
  return cnt_dict[n]

N = int(stdin.readline().strip())
cnt = find_cnt(N)
print(cnt % 10007)

여기서 추가된 것은 memoization 기법이다. 쉽게 말하면 메모하면서 문제를 푸는 것이다.

한번 계산한 것은 또 다시 계산하지 않도록 dictionary에 저장해놓는다. 

 

---

사용된 개념 : 재귀적 DP, memoization.