[백준 2024/09/28] 1904번 01타일

1. 문제

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

 

2. 접근 방법

n에 대해서 나열해 보면,

n = 1   -> 1개

n = 2   -> 2개

n = 3   -> 3개

n = 4   -> 5개

n = 5   -> 8개

n = 6   -> 13개

n = 7   -> 21개

n = 8   -> 34개

n = 9   -> 55개

n = 10   -> 89개

 

잘 보면 패턴을 확인할 수 있다. 그렇다. 피보나치 수열이다.

 

def fibo1(n, save):
    if n <= 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2

    b1 = 1
    b2 = 2
    result = 3
    for i in range(3, n+1, 1):
        result = b1 + b2
        b1 = b2
        b2 = result

    return result % 15746


if __name__ == "__main__":
    n = int(input())
    save = [-1] * (n+1)
    print(fibo1(n, save))

 

이렇게 돌리게 되면?! 시간 초과가 나게 된다.

따라서, result = (b1 + b2)%15746 이 된다.

왜냐? modulo 연산은 분배가 가능하기 때문이다. 

즉, 

 

이게 동일하다는 것이다.

 

두 코드가 동일한 결과를 반환하는 이유는, 모듈로 연산의 특성 때문에 덧셈 연산 후 모듈로 연산을 하든, 마지막에 한 번만 모듈로 연산을 하든, 최종 결과가 같기 때문입니다.

 

3. 코드

def fibo1(n, save):
    if n <= 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2

    b1 = 1
    b2 = 2
    result = 3
    for i in range(3, n+1, 1):
        result = (b1 + b2) % 15746
        b1 = b2
        b2 = result

    return result % 15746


if __name__ == "__main__":
    n = int(input())
    save = [-1] * (n+1)
    print(fibo1(n, save))