[백준] 1904번 01타일(feat. 다이나믹 프로그래밍, 메모리 제한)

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

 

 

문제 접근

• 첫번째 단계

문제의 조건을 정리하면 아래와 같다.

0과 1 타일이  있는데,
0타일은 00 이런식으로 두개씩 사용가능하다.
1타일은 낱개로 사용이 가능하다.

N이 주어졌을 때, N크기의 2진수열을 만든다면, 만들 수 있는 수열의 갯수를 구하는 것이다.

 예를 들어, 
n = 1일 때는 1만 단독으로 사용이 가능할 것이다.

n = 2 일 때는 00 or 11 이렇게 구성이 가능할 것이다.

이번에는 n = 3일 때를 생각해보자.
세칸이 있는데, 해당 3칸을 1칸과 2칸으로 나누어 생각해본다면, n = 1일때와 n = 2 일때를 포함하고 있는 것을 파악할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.(최적 부분 구조)
n = 3일때를 생각해보면, 3칸을 1칸(n = 1)과 2칸(n = 2)으로 나누어 생각할 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.(중복되는 부분 문제)
n = 3 문제는 n = 1문제와 n = 2문제를 포함하고 있다.

따라서, 이 문제는 다이나믹 프로그래밍으로 풀이를 진행할 수 있다.

 

 

 

• 두 번째 단계

DP Table을 정의해보자. 상태를 정의해보자는 의미이다.

n을 배열의 크기라고 생각하면,
dp[n]은 배열의 크기가 n일 때 만들 수 있는 배열의 가짓수로 정의할 수 있다.

그러면 dp[1]은 n이 1일때 취할 수 있는 배열의 가짓수가 될 것이고,
dp[2]는 n이 2일때 취할 수 있는 배열의 가짓수가 될 것이다.
그러면 dp[n]을 구하게 되면, 우리가 구하고자 하는 것과 같이 배열의 크기가 n일 때 취할 수 있는 배열의 가짓수를 구할 수 있을 것이다. 

 

• 세 번째 단계

점화식을 작성해보자.

n = 3 에서 연속으로 두개의 1타일이 배열되는 경우를 고려하지 않은 이유는,
n = 1 에서 1타일은 단독으로 사용 할 수 있는 것이 이미 고려되었기 때문이다.

 

코드 작성

# 입력 받기
n = int(input())

dp =[0] * 1000001

# n이 1인 경우 1만 단독으로 배열가능
dp[1] = 1
# n이 2인 경우 00 or 11 두가지로 배열가능
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 2] + dp[i - 1]) % 15746 # 메모리 제한으로 테스트케이스를 통과하지 못할 수 있으므로, 나머지를 바로 구해서 저장

print(dp[n])

위 점화식을 그대로 적용하였다.

배열의 인덱스는 0부터 시작이지만 가독성 좋은 코드를 작성하기 위해 0번 인덱스는 사용하지 않았다.

출력이 너무 커서 15746으로 나눈 값을 출력하게 되는데, 이 과정에서 주의해야 할 부분이 있다.

결과 값에만 나눠주는 게 아니라 반복문 안에서도 수시로 나머지 연산을 해 주어야 메모리 초과가 발생하지 않는다.
(처음에는 마지막 결과값에서만 나눠주는 로직으로 작성해서 코드를 제출했는데, 메모리제한 으로 인해 오답처리를 받았다.)

 

메모리 초과 문제에 대해서 고민을 해 본 결과 

리스트의 요소가 100만 자리면, 10이 2의 3승인 것을 고려하면,  최소 2의 300만승.
32승이 4바이트니까 숫자 하나당 대충 40만바이트씩 쓰고있는것. (100만 byte == 1mb)
근데 그런 숫자를 100만개 저장? 여기서 메모리 초과가 된 것이다.

정확한 사이즈 재보려고 sys.getsizeof 써서 dp찍어보면 나중에 나눠준거나 바로바로나눠준거나 똑같은 값이 나왔다.
이건 파이썬의 특성상, 리스트는 참조만 가지고 있기 때문에 발생하는 현상이었다.

리스트의 실제 크기를 찍어보려면, 리스트가 직접 참조하는 객체를 찍어봐야하는데,
파이썬 라이브러리 중에 래퍼런스된거까지 사이즈를 재주는 것이 있다.(라이브러리 이름은 찾아봐야한다..)

 

아무튼, 문제를 풀 때, 주어진 조건을 정확히 인지하고 고려하여 임해야겠다.