[백준/BOJ] 백준 코딩 알고리즘 1904번 01타일 Python 다이나믹 프로그래밍

 

첫 번째 풀이

import math

N = int(input())

res = []
for i in range((N // 2) + 1):
  if i == 0:
    res.append(1)
  else:
    res.append(math.comb(N - i, i))

print(sum(res) % 15746)

 

첫 번째 풀이에서는 수학적인 접근 방법을 사용했다

'00' 타일이 0, 1, 2, ... 개 일 때에 따라 몇 개의 경우의 수가 가능한지

math 라이브러리의 combination 함수를 사용하여 계산하였다

 

예) N = 5

'00' 타일이 0개일 때 → 1

'00' 타일이 1개일 때 → 5-1C1 → 4

'00' 타일이 2개일 때 → 5-2C2 → 3

총합 : 8

 

위 방법은 정답 자체는 맞으나,

시간초과로 인해서 문제가 발생했다.

 

 

두 번째 풀이

N = int(input())

MAX = 1000000
res = [0] * (MAX + 1)

res[1] = 1
res[2] = 2

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

print(res[N])

두 번째 풀이에서는 다이나믹 프로그래밍을 이용했다 (참고링크)

 

N이 1일 때는 '1'타일 1개만 들어갈 수 있고 → 경우의 수 1

N이 2일 때는 '00' 타일 1개 또는 '1' 타일이 2개 들어갈 수 있다 → 경우의 수 2

 

그리고 N이 3일 때부터 규칙이 적용되는데

다음과 같이 사고해볼 수 있다

'00' 또는 '11' 타일에 '1' 타일 붙이기 -> N이 2일 때의 경우의 수 : 2

'1'에 '00' 타일 붙이기 -> N이 1일 때의 경우의 수 : 1

 

즉, res[3] = res[1] + res[2]로 정리할 수 있고

이는 res[i] = res[i-2] + res[i-1]로 일반화할 수 있다

 

이렇게 모든 경우의 수에 대하여 답을 구한 뒤, 리스트에 저장하고

N 값에 해당하는 정답값을 내보내면 된다.

 

 

단, 이 때 연산되는 값의 크기가 매우 커 메모리 초과가 발생하기 때문에

리스트에 저장할 때 애초에 15746로 나눠서 저장해야 함에 유의할 필요가 있다