[정글 알고리즘] - [하] 백준1904- 01타일- 실버3

백준 · DP · 점화식 · 실버3

피보나치 형태의 점화식을 이용해 01 문자열 개수를 구하는 DP 문제

문제 링크 바로가기

문제 한눈에 보기

목표	길이 n인 01타일 수열의 개수 구하기
핵심 개념	DP, 점화식, 나머지 연산
점화식	dp[i] = dp[i-1] + dp[i-2]
주의	매 계산마다 15746으로 나눈 나머지를 저장해야 한다.

핵심 1

맨 뒤가 1로 끝나면 길이 i-1 문제로 연결된다.

핵심 2

맨 뒤가 00으로 끝나면 길이 i-2 문제로 연결된다.

핵심 3

그래서 결국 피보나치 형태 점화식이 나온다.

최종 코드

n = int(input())

def tile(n):
    if n == 1:
        return 1
    if 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]

print(tile(n))

주의할 점

제공한 초안 코드에서는 반복문이 range(4, n+1) 로 시작했는데, 이렇게 하면 dp[3] 이 계산되지 않아 값이 틀어진다. 반드시 3부터 시작해야 한다.

한 줄씩 설명

줄	코드	설명
1	n = int(input())	길이 n 입력.
3-7	if n == 1: return 1 if n == 2: return 2	초기값 처리.
9-11	dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2	DP 배열 생성과 시작값 설정.
13-14	for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) % 15746	작은 값부터 큰 값까지 차례대로 계산한다.
16	return dp[n]	정답 반환.

왜 점화식이 성립할까?

길이 i 타일 수열은 마지막이 1 로 끝나거나 00 으로 끝난다. 앞부분은 각각 길이 i-1, i-2 문제와 같으므로 두 경우를 더하면 된다.

한 문장 정리

01타일은 피보나치 형태 점화식을 이용하는 전형적인 DP 문제이며, 반복문을 3부터 시작하는 것이 중요하다.