[백준] 1904 : 01타일 (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/1904

문제

길이가 N인 이진 문자열을 만든다.

사용할 수 있는 조각은 다음 두 가지뿐이다.

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

길이가 정확히 N이 되도록 만들 수 있는 모든 경우의 수를 구하시오.

단, 결과는 15746으로 나눈 나머지를 출력한다.

---

입력

N

---

출력

길이가 N인 이진 문자열의 경우의 수 %15746

---

예제

입력

4

출력

5

---

정답 및 풀이

import sys
input = sys.stdin.readline

n =int(input())

dp = [0] * (n +2)
dp[1] =1
dp[2] =2

for iinrange(3, n +1):
    dp[i] = (dp[i -1] + dp[i -2]) %15746

print(dp[n])

풀이

1. dp = [0] * (n + 2)
   • dp[i]는 길이가 i인 이진 문자열을 만들 수 있는 경우의 수를 의미한다.
   • n이 1인 경우에도 dp[2]에 접근할 수 있도록 n + 2 크기로 배열을 생성한다.
   • 문자열 길이와 배열 인덱스를 그대로 대응시키기 위한 DP 배열이다.
2. dp[1] = 1
   • 길이가 1일 때는 "1"만 만들 수 있으므로 경우의 수는 1이다.
3. dp[2] = 2
   • 길이가 2일 때는 "11", "00" 두 가지가 가능하므로 경우의 수는 2이다.
4. for i in range(3, n + 1):
   • 길이 3부터 n까지 차례대로 경우의 수를 계산한다.
5. dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
   • 마지막이 "1"인 경우는 dp[i-1]가지이다.
   • 마지막이 "00"인 경우는 dp[i-2]가지이다.
   • 두 경우를 더한 뒤 값이 커지는 것을 방지하기 위해 15746으로 나눈 나머지를 저장한다.
6. print(dp[n])
   • 길이가 n인 이진 문자열을 만들 수 있는 최종 경우의 수를 출력한다.

---

새롭게 배운 내용 및 느낀점

• 마지막 상태를 기준으로 경우를 나누면 점화식을 세우기 쉽다는 것을 다시 느꼈다.
• 이 문제는 구조적으로 피보나치 수열과 동일한 형태의 DP 문제였다.
• DP 배열 크기를 넉넉하게 잡아 인덱스 오류를 방지하는 습관이 중요하다는 것을 배웠다.
• 큰 입력이 들어오는 문제에서는 모듈러 연산을 계산 과정 중에 해줘야 한다는 점을 확실히 이해했다.