[Python] 백준 1904번: 01타일

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

1904번: 01타일

 

일반화에 실패하여 이 문제의 특징을 파악하고자 시간복잡도를 통과하지 못하지만 정확성이 있는 코드를 작성하였다.

 

 

0이 8개, 1이 5개가 있을 때의 경우의 수는 무엇일까? 이를 중복조합을 통해 구할 수 있다. 위 사진의 경우에는 5개의 1이 5개의 공간들 중 1개씩 고르면 되므로, c0, c1이 각각 0, 1의 갯수(각각 8, 5)라고 했을 때, 다음의 식으로 구할 수 있다.

이것을 기반으로 코드를 작성하면 다음과 같다.

 

import sys
input = sys.stdin.readline

MOD = 15746


def get_factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
    return res


def get_combination(n, r):
    return get_factorial(n) // (get_factorial(r) * get_factorial(n-r))


def get_combination_with_repetition(n, r):
    return get_combination(n+r-1, r) % MOD


if __name__ == '__main__':
    N = int(input())

    res = 1
    for c0 in range(2, N+1, 2):
        c1 = N - c0
        res = (res + get_combination_with_repetition((c0//2)+1, c1)) % MOD
    print(res)

여기서 N을 1~100까지 설정하여 돌려본 결과는 다음과 같다.

피보나치 수열이다!

 

따라서 다음과 같은 코드를 작성하여 이 문제를 해결하였다.

import sys
input = sys.stdin.readline

MOD = 15746

if __name__ == '__main__':
    N = int(input())

    dp = [1, 1]
    pointer = 0
    for i in range(2, N+1):
        dp[pointer] = (dp[0] + dp[1]) % MOD
        pointer = (pointer + 1) % 2

    print(dp[(pointer+1) % 2])