[BOJ 1904] 01타일

문제 요약

길이가 N인 2진 수열을 만들 때, 사용할 수 있는 타일이

• 1 (길이 1)
• 00 (길이 2)

뿐이라고 하자. 이 타일들로 만들 수 있는 길이 N의 수열 개수를 구하고, 결과를 15746으로 나눈 나머지를 출력한다.

• 1 ≤ N ≤ 1,000,000

내가 풀었던 흐름

처음에 “이거 피보나치 아닌가?”라고 생각했다가,
중간에 개수를 잘못 세는 바람에 “아닌가?”라고 착각해서 순열/조합 쪽으로 한참 헤맸다.

그러다 GPT에게 힌트를 조금 받고 다시 보니까, 결국 전형적인 피보나치 형태 DP였다.

점화식 감각은 결국 다양한 DP 문제를 많이 풀면서 익혀야 할 것 같다.

점화식 세우기

길이 N을 만드는 방법을 생각하면 마지막에 붙는 타일은 둘 중 하나다.

1) 마지막이 1로 끝나는 경우

• 마지막에 1(길이 1)을 붙였다면,
• 앞부분은 길이 N-1을 만드는 경우의 수만큼 존재한다.

→ dp[N-1]

2) 마지막이 00으로 끝나는 경우

• 마지막에 00(길이 2)을 붙였다면,
• 앞부분은 길이 N-2를 만드는 경우의 수만큼 존재한다.

→ dp[N-2]

따라서,

• dp[N] = dp[N-1] + dp[N-2]

초기값은 문제 예시로 바로 확인 가능하다.

• dp[1] = 1 (1)
• dp[2] = 2 (00, 11)

즉, 피보나치와 같은 형태이고, 단지 모듈러(나머지) 연산만 추가하면 된다.

내 코드

n = int(input())

nums = [0, 1, 2]

for i in range(3, n + 1):
    nums.append((nums[i - 1] + nums[i - 2]) % 15746)

print(nums[n])

이번 문제로 배운 점

• “마지막 선택이 무엇인가”로 분해하면 점화식을 찾기 쉬운 경우가 많다.
  (마지막이 1이면 N-1, 마지막이 00이면 N-2)
• 겉보기엔 조합/순열처럼 보여도, 실제로는 DP(피보나치)로 떨어지는 문제가 많다.
• 점화식 찾는 감각은 결국 다양한 DP 문제를 풀면서 패턴을 몸에 익히는 게 중요하다고 느꼈다.
• N이 최대 1,000,000이므로 매 단계마다 mod를 해주지 않으면 수가 너무 커져서 메모리가 터진다.