[백준] 1904번 - 01타일 (DP) - 결과 포함

 

www.acmicpc.net/problem/1904

1904번: 01타일

이 문제 또한 전형적인 다이나믹 프로그래밍(DP) 문제이다.

다이나믹 프로그래밍 문제는 n =1 일 때, n = 2 일 때 .. 이렇게 직접 세보면서 풀리는 경우도 꽤 있는 것 같다.

 

이 문제를 보고나서 종이에 직접 경우의 수를 구해보았다.

문제에 나와있는 예시는 n = 1, 2, 4 인 경우가 나와 있기 때문에

3, 5, 6 까지 해보니까 확실한 규칙이 보였다.

 

n = 3 인 경우,

먼저 모두 0 인 경우는 존재하지 않는다.

0이 홀수개가 되기 때문이다.

 

1이 하나인 경우

1 0 0

0 0 1

 

1이 셋인 경우

1 1 1

 

이렇게 총 3가지의 경우가 나오고

 

n = 5 일 때는,

1이 한 개인 경우

0 0 0 0 1

0 0 1 0 0

1 0 0 0 0

 

1이 셋인 경우

0 0 1 1 1

1 0 0 1 1

1 1 0 0 1

1 1 1 0 0

 

1이 다섯인 경우

1 1 1 1 1

 

총 8가지 경우가 나온다.

 

n = 6일 때는 총 13가지의 경우가 나오는 것을 확인할 수 있다.

 

순서대로

1, 2, 3, 5, 8, 13 . . .

어디서 많이 본듯한 수열의 형태였다.

 

바로 피보나치 수열과 같은 형태를 보이고 있었다.

 

피보나치 수열을 구현하는 것은 어렵지 않았지만

입력의 조건인 N 이 1,000,000 까지 가능하기 때문에 일반적인 재귀 피보나치는 적합하지 않았다.

 

이전에 사용했던 메모이제이션 방법과 반복문을 이용한 피보나치 수열로 문제를 해결했다.

 

[소스 코드]

import sys


n = int(sys.stdin.readline().rstrip())
d = [0] * (n + 1)
d[1] = 1
if n > 1:
    d[2] = 2

if n != 1 or n != 2:
    for i in range(3, n + 1):
        d[i] = (d[i - 1] + d[i - 2]) % 15746

print(d[n])