BOJ 1904 DP 풀이: 조합의 덫에서 벗어나 피보나치로!

1904번 문제, "01 타일"을 풀면서 DP 경험을 늘렸습니다. 처음에는 수학적인 조합론으로 접근하려 했지만, 문제의 출제 의도대로 DP로 전환하는 과정에서 많은 것을 배웠습니다. 학습한 내용을 공유하며, 이 문제가 왜 DP로 풀리는지 다뤄보겠습니다.

학습 주제

• 오늘 공부한 주제: 백준 온라인 저지 1904번 "01 타일" 문제 풀이
• 학습 날짜: 2026년 2월 11일

질문과 탐구

처음 문제를 접했을 때, 제 머릿속에는 다음과 같은 질문들이 떠올랐습니다.

• 길이 N을 만들기 위해 00 타일과 1 타일을 어떻게 조합할 수 있을까?
• 타일의 순서를 고려하지 않고, 단순히 길이 N을 구성하는 00과 1 타일의 개수 조합만 구해보면 어떨까?
• 조합을 계산할 때 모듈러 연산이 등장했는데, 이는 어떤 의미를 가지는가?

이런 궁금증들을 해결하기 위해 처음에는 2x + y = n (여기서 x는 00 타일 개수, y는 1 타일 개수) 방정식을 세우고, 가능한 (x, y) 조합을 구한 뒤 조합론 공식을 적용하는 방향으로 탐구를 시작했습니다.

핵심 학습 내용

처음 접근했던 수학적인 방식의 한계와 DP로 풀어야 하는 이유를 명확히 이해할 수 있었습니다.

1. 조합론적 접근의 함정

저는 2x + y = n 관계에서 가능한 x 값의 범위 (0부터 n/2까지)를 반복하며, 각 경우에 대해 (x+y) C y (전체 타일 개수 중 1 타일 개수를 선택하는 경우의 수)를 계산하는 방식으로 접근하려 했습니다.

• 제가 세운 수식:
  $$\sum _{x=0}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-x}{x}\right)$$

이 수식 자체는 수학적으로는 **완전히 올바른 피보나치 수열의 닫힌 형태(closed form)**임이 밝혀졌습니다. 하지만 문제의 핵심 함정은 바로 모듈러(MOD) 값에 있었습니다.

• 문제의 MOD: 15746 (이는 소수가 아닌 합성수입니다.)
• 문제점: 조합 계산 시 필요한 모듈러 역원(modular inverse)은 MOD가 소수일 때만 항상 존재합니다. MOD가 합성수이면 역원이 존재하지 않아, 팩토리얼 기반의 조합 계산이 원천적으로 불가능해집니다.

즉, 제가 세운 수학적 아이디어는 옳았지만, 문제에서 제시된 MOD 값 때문에 실질적인 구현이 불가능했던 것입니다.

2. DP로의 전환: 문제의 본질 파악

이 문제의 출제 의도는 조합론적 접근을 봉쇄하고 DP를 사용하게 만드는 것이었습니다. DP 관점에서 문제를 다시 바라보면 다음과 같습니다.

• 상태 정의: dp[i] = 길이가 i인 이진 문자열을 00과 1 타일로 만드는 경우의 수.
• 점화식: 길이가 i인 문자열을 만드는 마지막 타일은 1이거나 00입니다.
  • 마지막이 1이면: 앞 부분은 길이 i-1이므로 dp[i-1]가지 경우.
  • 마지막이 00이면: 앞 부분은 길이 i-2이므로 dp[i-2]가지 경우.
  • 따라서 dp[i] = dp[i-1] + dp[i-2] (피보나치 수열과 동일한 형태)
• 초기값:
  • dp[1] = 1 (길이 1: "1")
  • dp[2] = 2 (길이 2: "11", "00")

이 점화식과 초기값을 통해 n까지 dp 값을 계산하면 됩니다.

3. 모듈러 연산의 역할

n의 최대값이 1,000,000이기 때문에 dp 값이 기하급수적으로 커집니다. 이때 MOD = 15746을 사용하여 계산 중간중간 모듈러 연산을 적용해야 합니다. 모듈러 연산의 성질 (a + b) % m = ((a % m) + (b % m)) % m 덕분에, 덧셈 연산에서 중간 결과를 계속 모듈러 값으로 유지해도 최종 결과는 동일합니다. 이는 조합론 접근을 못하게하는 동시에, DP 계산을 수행할 수 있게 하는 핵심 장치였습니다.

이해한 내용

• 조합론적 접근의 한계: MOD가 소수가 아닐 때 팩토리얼 기반의 조합 계산은 불가능하다는 것을 알게 되었습니다.
• DP의 본질: 문제를 작은 단위로 쪼개고, 마지막 상태를 기준으로 이전 상태와의 관계(점화식)를 정의하는 것이 DP의 핵심임을 다시 한번 느꼈습니다.
• 피보나치와 조합의 관계: n을 1과 2의 합으로 분할하는 경우의 수와 특정 조합 합이 피보나치 수열과 같다는 사실을 배웠습니다. (이는 ∑binom(n-x, x) = F_{n+1} 이라는 조합론의 중요한 정리입니다.)
• 초기값의 중요성: DP에서 초기값은 공식이 아니라 문제 정의를 직접 세어서 결정해야 한다는 것을 배웠습니다. dp[1]=1, dp[2]=2는 문제의 고유한 특징을 나타냅니다.
• 모듈러 연산의 안정성: 덧셈 연산에서의 모듈러 연산의 성질을 통해, 큰 수를 안전하게 계산할 수 있다는 것을 이해했습니다.

실전 적용

• 이 지식을 어디에 적용할 수 있을지:
  • 타일링 문제 (BOJ 17501, 2n 타일링 등)
  • 계단 오르기 문제 (1칸 또는 2칸씩 오르는 경우)
  • LIS(Longest Increasing Subsequence)와 같이 이전 상태를 기반으로 현재 상태를 계산하는 모든 DP 문제

참고 자료

AI와의 대화에서 직접적으로 언급된 공식 문서는 없었지만, 논의 과정에서 다음과 같은 개념들이 핵심적인 역할을 했습니다.

• 피보나치 수열의 정의: F(n) = F(n-1) + F(n-2)
• 모듈러 연산의 성질: (a + b) % m = ((a % m) + (b % m)) % m
• 조합론의 기본 정의: n개 중 k개를 순서 상관없이 선택하는 경우의 수 binom(n, k)
• 조합론 정리: ∑_{x=0}^{⌊n/2⌋} \binom{n-x}{x} = F_{n+1} (이항 계수의 합과 피보나치 수열의 관계)

이 정리를 통해, 처음에 수학적으로 세웠던 조합 공식이 사실은 피보나치 수열의 다른 표현임을 알게 되었습니다. 오늘 학습은 단순히 알고리즘 문제 하나를 푸는 것을 넘어, 수학적 아이디어가 알고리즘적 사고와 어떻게 연결되는지를 이해하는 소중한 경험이었습니다.