[DP] 백준 #1904 01타일 - python

🗂️ 문제

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

 

💡 접근법

00과 1을 조합하여 N자리의 수를 만드는 문제이다.

문제에서는 제시하는 자릿수에 따라 만들 수 있는 수의 개수가 달라진다. 규칙을 찾아보기 위해 다음과 같이 N에 따라 가능한 경우를 나열해보았다.

 

N=1일 때, 1 ⇒ 1개
N=2일 때, 11, 00 ⇒ 2개
N=3일 때, 001, 100, 111 ⇒ 3개
N=4일 때, 1111, 0011, 1001, 1100, 0000 ⇒ 5개
N=5일 때, 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 ⇒ 8개

 

규칙을 보니 DP인 걸 단숨에 알아낼 수 있었다. 하지만 왜 DP인가를 생각해보면, 그 이유는 다음과 같다.

 

• 2진 수열의 마지막이 “1”인 경우 → 그 앞 부분은 길이가 N-1인 2진 수열이다. 따라서 길이가 N-1인 경우의 개수와 같다.
• 2진 수열의 마지막이 “00”인 경우 → 그 앞 부분은 길이가 N-2인 2진 수열이다. 따라서 길이가 N-2인 경우의 개수와 같다.

따라서 자릿수가 N일 때 2진 수열이 1로 끝나는 경우와 00으로 끝나는 경우를 더하면 모든 경우를 구하는게 된다.

이를 점화식으로 나타내면 dp[i] = dp[i-1]+ dp[i-2] (i≥3)으로, 피보나치 수열과 동일하다.

즉, 작은 문제의 해를 이용하여 큰 문제를 풀 수 있으므로 DP의 조건을 만족한다.

 

 

하지만 마지막에 메모리 초과 에러가 발생했다.

파이썬의 int는 C나 Java처럼 고정된 바이트 크기를 가지지 않고 가변 길이를 갖는다. 따라서 저장하는 숫자의 크기가 커지면 동적으로 바이트 크기도 커진다.

위와 같은 파이썬의 특성으로 인해 메모리 초과 에러가 발생한 것이다. 따라서 값을 저장할 때 가능한 작은 수를 저장해야 한다.

 

문제에서 출력 시 15746으로 나눈 값을 출력하라고 했다. 이에 따라 가능한 출력의 최댓값은 15745이므로, DP 배열에 값을 저장해 둘 때 15746으로 나눈 값을 저장해두어도 된다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
dp = [0] * (N+1)
dp[1] = 1

if N == 1:
    print(dp[1])
else:
    dp[2] = 2
    
    for i in range(3, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746

    print(dp[N] % 15746)

 

🧐 배운 점

• 파이썬의 int, str은 가변 크기의 자료형을 가지므로 숫자의 크기에 따라 차지하는 메모리 크기가 달라진다. 반면, float는 고정 크기(24바이트)를 갖는다.

 

✅ 정답 확인