[알고리즘/baekjoon] 11726_2×N 타일링(python)

문제

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

11726번: 2×n 타일링

# 전형적인 다이나믹 프로그래밍 문제이다.

# 문제를 처음 접했을 때 아무런 공식이나 풀이방법이 떠오르지 않는다면 하나하나 예시를 들면서 공식을 찾는것이 좋은 방법이다. 특히나 dp문제에서는 더 더욱 !

# 여기서는 dp[i] = dp[i-1] + dp[i-2] 라는 점화식을 발견할 수 있다.

import sys

N = int(sys.stdin.readline())
dp = [0 for _ in range(N+1)]

if N <3:
  print(N)
else: # 본격적으로 n이 3부터 점화식이 적용
  dp[1] = 1
  dp[2] = 2
  for i in range(3,N+1):
    dp[i] = dp[i-1] + dp[i-2]
  print(dp[N]%10007)

# 예시

# n = 1 (|) -> 1

# n = 2 (||, =) -> 2

# n = 3 (|||, |=, =|) -> 3

# n = 4 (||||, =||, |=|, ||=, ==) -> 5

# n = 5 (|||||, =|||, |=||, ||=|, |||=, |==, =|=, ==|) -> 8

# n의 경우의 수는 n-1의 경우의 수와 n-2의 경우의 수의 합과 같다. (단, n이 3이상일 때)

 

* 코드 참조는 아래 github주소를 들어와주세요

https://github.com/JunSeokCheon

JunSeokCheon - Overview