1904 01타일 _python

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

1904번: 01타일

메모리초과

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

각 테스트케이스를 순서대로 쓰나보니 패턴이 보였다.

1번: 1
2번: 00 11
3번: 001 100 111
4번: 0011 0000 1001 1100 1111
5번: 00001 00100 00111 10000 10011 11001 11100 11111

 

여기서 4번을 보면

2가지 경우로 나눠서 볼 수 있다.

3번의 001 100 111의 앞에 1이 붙는 경우 -> 1001 100 1111

2번의 00 11의 앞에 00이 붙는 경우 -> 0000 0011

이러면 총 5개다.

5번의 경우도 마찬가지로 3번의 경우에 00이 붙이거나 4번의 경우에 1을 붙이는 경우를 합하면 나온다.

그러면 점화식이 완성된다.

dp[n] = dp[n-1] + dp[n-2]

 

메모리초과가 발생한다면 

출력에 15746을 잘 생각하고, 테스트케이스가 1000000이라면 어떨지 생각해보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""

"""

N = int(input())
dp = [1,2]

for i in range(2,N):
    dp.append((dp[i-1]+dp[i-2])%15746)
print(dp[N-1])

408ms