문제 출처 : https://www.acmicpc.net/problem/1904
문제 파악
타일의 종류는 두 가지다.
1(길이 1)00(길이 2)
길이 N짜리 1차원 벽을 이 두 타일로 가득 채우는 방법의 수를 구하는 문제다.
단, 답은 15746으로 나눈 나머지를 출력해야 한다.
핵심 아이디어
이 문제는 단순 조합 문제가 아니라 이전 결과가 다음 결과에 영향을 주는 구조이기 때문에
Bottom-up Dynamic Programming(DP)으로 접근할 수 있다.
점화식 도출 과정
N = 1
가능한 조합:
1 → 총 1개
N = 2
가능한 조합:
00, 11 → 총 2개
N = 3
가능한 조합:
100, 001, 111 → 총 3개
잘못된 접근 (앞뒤에 붙이기)
처음엔 “이전 타일 조합의 앞뒤에 00이나 1을 붙이자”고 생각할 수 있다.
N=4일 때,N=2조합에00을 앞뒤로 붙이기N=3조합에1을 앞뒤로 붙이기
→ 하지만 이 방식은 중복이 발생한다.
중복 없는 접근
맨 앞에만 붙이기로 하자.
N-1조합 앞에1을 붙인다.N-2조합 앞에00을 붙인다.
이 두 경우는 절대 겹치지 않는다.
결국 다음 점화식이 완성된다.
dp[n] = dp[n-1] + dp[n-2]
→ 즉, 피보나치 수열 구조와 동일함을 알 수 있다.
⚙️ 구현 코드
import sys
input = sys.stdin.readline
N = int(input())
dp = [0] * (N + 2) # N + 1 까지만들경우 N이 1인경우 인덱스 에러가 남
dp[1] = 1
dp[2] = 2
for i in range(3, N + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
print(dp[N])
Frontend Engineers