[백준 1904번] 01타일

이번 문제는 간단히 정리하자면 주어진 n의 자리수를 가지며 00과 1을 가지고 만들 수 있는 문자열의 개수를 구하는 문제이다.

 

처음에 이 문제를 보았을 때 왜 이게 DP 문제이고, 어떤 방식으로 문제를 풀어야 할지 감도 오지않았고, 결국 30분정도 고민하다가 풀이 접근 방법에 대해 이해하기 위하여 다른 분의 풀이를 참고하였다 😢

 

다른 분들의 풀이마저도 처음에 이해하기 어려웠기 때문에 직접 n=1(일의 자리수)부터 n=5(만의 자리수) 까지 종이에 적어보면서 이해해보기로 하였다.

 

다른 분들의 풀이를 참고하고 경우의 수를 직접 손으로 적어보니 이 문제가 왜 DP 문제인지 새삼 알 수 있었다.

 

1) 문제 접근법

n = 1 : 1
n = 2 : 00, 11
n = 3 : 100, 001,  111
n = 4 : 0000, 0011, 1001, 1100, 1111
n = 5 : 00111, 10011, 11001, 11100, 00001, 10000, 00100, 11111 

위는 n=1 부터 n=5 까지의 경우의 수를 나열한 것인데, 여기서 잘 보면 n=3 부터 개수의 패턴이 'n의 경우의 수 = (n-1) 경우의 수 + (n-2) 경우의 수' 인 것을 확인할 수 있다 !

 

n = 1 : 1
n = 2 : 00, 11
n = 3 : 100, 001,  111
n = 4 : 0000, 0011, 1001, 1100, 1111
n = 5 : 00111, 10011, 11001, 11100, 00001, 10000, 00100, 11111 

이게 왜 이렇게 되는지는 바로 이해하기는 쉽지 않은데, 위 예시의 색깔을 주목해보자.

 

경우의 수를 나열해보면 n번째의 경우의 수가 'n-2번째의 경우 + 00' + 'n-1번째의 경우 + 1'인 문자열로 이루어져 있다는 것을 알 수 있다. ⭐️⭐️⭐️⭐️⭐️

 

결국, 정리하자면 피보나치 수열처럼 n=1 과 n=2 인 경우를 미리 정의하고, n=3 부터는 d[n] = d[n-2] + d[n-1] 이라는 점화식을 적용시킬 수 있다 !

---

2) 풀이 과정

문제를 이해하고 나서 처음으로 푼 방법은 DP 알고리즘 풀이 중에서도 '재귀함수'를 사용하여 푸는 Top-Down 방식이었다.

import sys
sys.setrecursionlimit(10**6)

n = int(input())

dp = [0]*1000001

def solution(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    if dp[n]:
        return dp[n]
    dp[n] = solution(n-2) + solution(n-1)
    return dp[n]%15746

print(solution(n))

하지만, 이번 문제를 풀면서 느낀 것이지만 재귀함수를 사용하는 Top-Down 방식은 계산 속도가 느려 성능이 좋지 않고 RecursionError가 발생하는 등의 문제가 많았다.

 

따라서 '재귀함수'를 사용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 Top-Down 방식이 아니라 '반복문'을 사용하여 작은 문제부터 차근차근 답을 도출해내는 Bottom-Up 방식을 사용하기로 하였다. 😎

 

n = int(input())

dp = [0]*1000001

dp[0] = 1
dp[1] = 2

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

print(dp[n-1])

Bottom-Up 방식을 사용하고나니 코드도 훨씬 깔끔해지고, 시간 초과없이 문제를 통과할 수 있었다 !

(그리고 마지막에 %15746 을 해주면 메모리 초과가 발생하기 때문에 값을 저장하기 전에 %15746을 해주어야 통과할 수 있다)

 

이번 문제를 통해 배우게 된 점은 다음과 같다.

 

1. 문제가 감이 오지 않거나, DP 문제인지 파악하기 위해서는 작은 문제의 경우의 수부터 패턴이 보일 때까지 나열해보자(점화식 유도).

2. DP 문제를 풀이할 때 가능하다면 재귀 함수를 이용하는 Top-Down 방식보다는 반복문을 이용하는 Bottom-Up 방식으로 구현하자 !