1 분 소요

백준 1904번 01타일 문제 풀이를 해보겠습니다.

출처 : 백준

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

풀이

문제 설명: 점화식의 값을 특정 상수로 나눈 나머지를 구하는 문제

n이 1일때는 1만 가능하고, n이 2일때는 11,00 그리고 n이 3일때는 100, 001, 111이 가능하다.

n이 4일때는 1100, 1001, 0011, 1111, 0000이 가능하다.

즉, 아래와 같은 점화식이 만들어진다.

  • tile(3) = tile(2) + tile(1)
  • tile(4) = tile(3) + tile(2)
  • tile(n) = tile(n-1) + tile(n-2)

하지만 문제에서는 1,000,000까지의 N이 주어지고 tile(N)의 값이 매우 커질 수 있어서 15746으로 나눈 나머지를 저장한다.

코드

import sys
input = sys.stdin.readline

def tile(n) :
    if n == 1 :
        return 1
    elif n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n+1) :
        dp[i] = (dp[i-1] + dp[i-2]) % 15746

    return dp[n]


def main():
    N = int(input().strip())
    print(tile(N))

main()

댓글남기기

참고