[python] 1904. 01타일

• 문제 

---

 

 

• 잘못된 풀이 (런타임에러, 메모리초과)

N = int(input())

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

for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % 15746)

 

해당 코드로 작성하면 런타임에러와 메모리초과가 발생한다.

 

파이썬은 int형의 고정된 크기가 아니다.

그 변수가 실제로 담고 있는 값의 크기에 따라, 유동적으로 사용하는 메모리가 변한다.

수가 매우 커지게 되면 그 수를 정확하게 표현하기 위해 점점 더 많은 메모리를 할당받게 되는데, 

해당 문제의 경우 무턱대고 모든 항의 값을 다 구하려고 하면 N에 비례하여 자릿수가 점점 늘어나기 때문에 

총 사용하게 되는 공간 복잡도가 O(N^2)가 된다.

 

배열을 쓰지 않고 한정된 변수들 사이에서 돌려가면서 처리하면 공간 문제는 해결하겠지만

여전히 시간 복잡도가 O(N^2)이기 때문에 통과할 수 없다. 

 

따라서 해당 문제와 같이 나머지를 출력하는 경우에는 먼저 답을 구하고 마지막에 나머지 연산을 하는 것이 아니라,

연산 과정에서의 모듈로 수를 계속 작게 유지할 수 있도록 같이 연산을 해야 한다. 

 

그렇기 때문에 아래와 같이 코드를 수정하였다. 

 

 

 

 

• 올바른 풀이

N = int(input())

dp = [0] * 1000001
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])

 

해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다.

00 혹은 1로 타일을 구성하는 문제로, dp를 하나씩 살펴보면 다음과 같다.

dp[1] = 1 → 1개

dp[2] = 11, 00 → 2개

dp[3] = 111, 001, 100 → 3개

dp[4] = 1111, 0011, 1001, 1100, 0000 → 5개 

 

정리해보면, dp[i] = dp[i-1] + dp[i-2]와 같다.

왜냐하면 문제 풀이의 방법론이 i-1에는 1을 붙이고, i-2에는 00을 붙이는 것이기 때문이다.