[알고리즘] 백준 1904번 : 01타일

백준 1904번 : 문제집 (문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 동적 프로그래밍
• 난이도 : 하

소스코드

• 주의 : 아래에서 cache를 [0] * 1000001가 아니라 cache = [0] * (n+1)으로 작성하면 n=1 일 때, cache = [0, 0]이므로 cache[2] = 2 에서 IndexError가 발생한다.

import sys

n = int(sys.stdin.readline())

cache = [0] * 1000001

cache[1] = 1
cache[2] = 2

for i in range(3, n+1):
    cache[i] = (cache[i-2] + cache[i-1]) % 15746

print(cache[n])

설명

• 동적 프로그래밍문제의 가장 기본적이면서, 전형적인 문제이다. (반드시 알아두기!)
• n이 최대 1,000,000이므로, O(n)시간으로 해결해야 한다.
• n=1일 때 => 1로 한 가지, n=2일 때 => 11, 00로 두 가지 만들기 가능.
• 타일을 오른쪽에서 부터 이어 붙인다고 할 때, 길이가 i인 수열을 형성하는 방법은 아래 두 가지 뿐이다.
  

  

  • 예를 들어, n=3인 수열을 만들고자 한다.
  • 이미지와 같이 맨 끝이 1일 때 그 앞에 길이가 i-1 = 2인 수열(11, 00)을 이어 붙이면 111, 001
  • 이미지와 같이 맨 끝이 00일 때 그 앞에 길이가 i-2 = 1인 수열(1)을 이어 붙이면 100. 총 3가지 수열을 만들 수 있다.
  • 결국 ai가 수열의 길이가 i일 때 만들 수 있는 수열의 개수라고 하면, a3 = a1 + a2라는 식을 세울 수 있다.
• 즉, ai = ai-2 + ai-1 이 되는 것이다. 이 문제는 결국 피보나치 수열과 동일한 문제이다.