[BOJ/python] 1904: 01타일

문제

✔️ silver 3

문제 흐름

1x2 타일이었나 이런 문제를 전에 마주친 기억이 난다.
아무래도 이 문제가 그 문제보다 쉬울 것 같다.

경우의 수이기 때문에 dp 접근을 생각해볼 수 있다.

앞서 몇가지 패턴을 살펴봐보자.

memo[i]를 현재 타일으로 i 자릿수의 2진수를 만들 수 있는 경우의 수 라고 가정할 때,
memo[i]는 i-1의 경우의 수에 1을 붙여준 경우의 수와 i-2의 경우의 수에 0 0을 붙여준 경우의 수를 모두 합쳐 구할 수 있음을 알 수 있다.
따라서 앞에 시작점 1이 빠진 피보나치 수열과 같다.

피보나치 수열이라는 것을 알았으면 이해와 구현은 확 쉬워진다.
근데 여기서 첫번째 제출은 메모리 초과, 두번째 제출은 시간 초과를 맞는다.
왜냐?
조건이 1 ≤ N ≤ 1000,000이기 때문이다!!!!

처음 조건을 확인하고 모든 수열을 저장하는건 포기하고, 다음 수 계산에 필요한 최종 두개만 저장하기로 했다.
그래도 시간초과가 떠서 고민을 많이 했다.
더해서 다음 값을 구하는 로직을 어떻게 더 단순화할 수 있다는 것인가???

질문 게시판을 뒤졌고 이유를 알 수 있었다.

전혀 생각 못했는데 컴퓨터도 숫자가 커지면 계산이 느려진다고 한다.
넌 컴퓨터잖아....
그래서 (a + b) % c == (a % c + b % c) % c를 적용시켜 계산을 향상시켰고,
시간 초과를 피할 수 있었다. ^^

코드

# 01타일
# dp

import sys
input = sys.stdin.readline

def dp(n: int):
    # memo[i]: i자릿수의 2진수를 만들 수 있는 경우의 수
    # n <= 1000,000 이기 때문에 memo[i] 계산에 필요한 memo[i-1], memo[i-2]만 저장
    if n == 1:
        return 1
    elif n == 2:
        return 2
    memo_1 = 1
    memo_2 = 2

    for i in range(3, n+1):
        memo_2, memo_1 = (memo_1 + memo_2) % 15746, memo_2 % 15746
    
    return memo_2

if __name__ == "__main__":
    n = int(input())

    result = dp(n) % 15746
    print(result)