Note
동적 프로그래밍을 활용하여 피보나치 수열과 유사한 패턴의 문제를 해결하는 문제입니다.
문제
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.
어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.
그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.
문제 링크: https://www.acmicpc.net/problem/1904
입력
첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력
첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
예제
예제 입력 1:
4
예제 출력 1:
5
문제 원리 분석
이 문제는 동적 프로그래밍을 사용하여 해결할 수 있는 전형적인 문제입니다.
핵심 이해
- 사용 가능한 타일:
1(길이 1)00(길이 2, 0은 반드시 쌍으로만 사용 가능)
- 목표: 길이 N인 2진 수열을 만들 수 있는 모든 경우의 수
작은 예시로 패턴 찾기
| N | 가능한 수열 | 개수 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 00, 11 | 2 |
| 3 | 100, 001, 111 | 3 |
| 4 | 0011, 0000, 1001, 1100, 1111 | 5 |
점화식 유도
길이 i인 수열을 만들 때, 마지막에 올 수 있는 타일을 기준으로 생각해봅시다:
-
마지막이
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인 수열은00,11가능
피보나치 수열과의 관계
| i | dp[i] | 피보나치 |
|---|---|---|
| 1 | 1 | fib(1) = 1 |
| 2 | 2 | fib(2) = 1 |
| 3 | 3 | fib(3) = 2 |
| 4 | 5 | fib(4) = 3 |
| 5 | 8 | fib(5) = 5 |
실제로는 피보나치 수열의 인덱스가 하나씩 밀려있는 형태입니다:
dp[i] = fib(i+1)(단, fib(1)=1, fib(2)=1로 정의할 때)
코드 구조 분석
제공된 코드
dn = [0] * 1000001
dn[0] = 1
dn[1] = 2
dn[2] = 3
dn[3] = 5
n = int(input())
for i in range(4, n + 1):
dn[i] = (dn[i - 2] + dn[i - 1]) % 15746
print(dn[n-1])코드 분석
1. 배열 초기화
dn = [0] * 1000001- 최대 N이 1,000,000이므로 배열 크기를 1,000,001로 설정
- 인덱스 0부터 1,000,000까지 사용 가능
2. 초기 값 설정
dn[0] = 1
dn[1] = 2
dn[2] = 3
dn[3] = 5이 초기화는 인덱스가 하나씩 밀려있는 구조입니다:
dn[0] = 1→ 실제로는 길이 1인 경우 (dp[1] = 1)dn[1] = 2→ 실제로는 길이 2인 경우 (dp[2] = 2)dn[2] = 3→ 실제로는 길이 3인 경우 (dp[3] = 3)dn[3] = 5→ 실제로는 길이 4인 경우 (dp[4] = 5)
3. 점화식 적용
for i in range(4, n + 1):
dn[i] = (dn[i - 2] + dn[i - 1]) % 15746i = 4부터 시작 (이미dn[0],dn[1],dn[2],dn[3]은 초기화됨)- 점화식:
dn[i] = dn[i-2] + dn[i-1] - 모듈로 연산: 매번 15746으로 나눈 나머지를 저장하여 오버플로우 방지
4. 결과 출력
print(dn[n-1])- 입력
n에 대해dn[n-1]을 출력 - 인덱스가 하나씩 밀려있으므로
n-1을 사용
코드의 특징
장점
- 모듈로 연산: 매 반복마다
% 15746을 수행하여 큰 수 연산을 방지 - 미리 초기화: 작은 값들을 미리 설정하여 루프를 간소화
- 충분한 배열 크기: 최대 입력 크기에 맞게 배열을 미리 할당
주의사항
- 인덱스 혼동:
dn[0]이 실제로는 길이 1을 의미하므로, 인덱스와 실제 길이의 관계를 명확히 이해해야 함 - 출력 인덱스:
dn[n-1]을 출력하는 것이 올바른지 확인 필요
올바른 구현 (명확한 버전)
더 명확하게 작성한다면:
MOD = 15746
n = int(input())
# dp[i] = 길이 i인 수열의 경우의 수
dp = [0] * (n + 1)
# 초기 조건
dp[1] = 1 # 길이 1: "1"
dp[2] = 2 # 길이 2: "00", "11"
# 점화식 적용
for i in range(3, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
print(dp[n])이 버전이 더 직관적이고 이해하기 쉽습니다.
시간 및 공간 복잡도
시간 복잡도
- O(N): 반복문이 4부터 n까지 실행되므로 최대 1,000,000번 반복
- 각 반복에서 상수 시간 연산만 수행
공간 복잡도
- O(N): 배열
dn이 최대 1,000,001 크기 - 최적화 가능: 마지막 두 값만 저장하면 O(1) 공간으로도 해결 가능
공간 최적화 버전
MOD = 15746
n = int(input())
if n == 1:
print(1)
elif n == 2:
print(2)
else:
a, b = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1):
a, b = b, (a + b) % MOD
print(b)이렇게 하면 O(1) 추가 공간만 사용합니다.
예제 동작 과정
예제: n = 4
초기화:
dn[0] = 1 (길이 1: "1")
dn[1] = 2 (길이 2: "00", "11")
dn[2] = 3 (길이 3: "100", "001", "111")
dn[3] = 5 (길이 4: "0011", "0000", "1001", "1100", "1111")
루프 실행:
i = 4: 이미dn[3] = 5로 초기화되어 있음- 실제로는 루프가 실행되지 않음 (range(4, 5)는 비어있음)
출력:
dn[4-1] = dn[3] = 5출력
예제: n = 5
초기화 후:
dn[0] = 1
dn[1] = 2
dn[2] = 3
dn[3] = 5
루프 실행:
i = 4:dn[4] = (dn[2] + dn[3]) % 15746 = (3 + 5) % 15746 = 8i = 5:dn[5] = (dn[3] + dn[4]) % 15746 = (5 + 8) % 15746 = 13
출력:
dn[5-1] = dn[4] = 8출력