[백준][python] 1904.01타일 - 동적계획법

문제

• 백준 1904 01타일 Silver III
• python
• 문제링크

1904번: 01타일

나의 코드

한 문제에서 메모리초과 시간초과가 모두 나본 것은 또 처음인 것 같다..

이 문제는 패턴만 찾으면 쉽게 풀 수 있다. 

N = 1 -> 1

N = 2 -> 00

N = 3 -> 001, 100, 111

N = 4 -> 0011, 0000, 1001, 1100, 1111

N = 5 -> 00111, 00001, 00100, 10011, 10000, 11001, 11100, 11111

.

.

1, 2, 3, 5, 8 .... 의 피보나치 수열을 따른다.

따라서 동적계획법을 따르는 피보나치 수열로 구현하면 쉽게 풀 수 있다. 단, 주의할 점은 문제에서 주는 맥시멈의 N 값이 100000이기 때문에 흔한 메모이제이션 문제에서 풀듯 미리 모든 배열을 생성해두면 메모리 초과가 발생할 수 있다. + 코드 자체에서는 테스트 케이스가 한번만 돌아가기 때문에 N 길이의 배열만 생성하는 것이 바람직하다.

lst = [0, 1, 2]

N = int(input())

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

print(lst[N])

동적 계획법은 풀어도 풀어도 어렵다..ㅠㅠ 점화식 만드는게 제일 어려운 것 같다 흑흑