[알고리즘] 동적 계획법(Dynamic Programming) - 백준 1904번 01타일

정답 코드

N = int(input())

def solution(N):
    tile = [0] *  1000001
    tile[1] = 1
    tile[2] = 2
    for i in range(3, N+1):
        tile[i] = (tile[i-1] + tile[i-2]) % 15746
    
    return tile[N]

print(solution(N))

풀이과정

N = 1 일 때 '1개' => 1
N = 2 일 때 '2개' => 00, 11
N = 3 일 때 '3개' => 001, 100, 111
N = 4 일 때 '5개' => 0011, 0000, 1001, 1100, 1111
N = 5 일 때 '8개' => 00111, 00001, 00100, 11111, 11001, 11100, 10000, 10011

길이가 N인 2진 수열의 개수 = 길이가 N-1인 2진 수열의 개수 + 길이가 N-2인 2진 수열의 개수

주의할 점

반복문을 돌때마다 나머지 연산을 하지 않으면 오버플로우가 발생한다.