[백준 1904번] 01 타일 - 파이썬

! 개인 기록용으로 TIL을 작성하며 한 번 더 정리해보는 것이라 코드가 완벽하지 않거나 정리가 미흡할 수 있습니다.

 

 

www.acmicpc.net/problem/1904

1904번: 01타일

 

[백준 1904번] 01타일 문제

 

 

---

 

 

03월 19일 금요일 알고리즘 테스트에 나온 문제라 다시 한 번 정리해볼겸 작성한다.

 

문제를 요약하면 자연수 n = 1일때 만들 수 있는 숫자는 1이다.

자연수 n = 2일 때는 00, 11을 만들 수 있고, 자연수 n = 4일 때는 0011, 0000, 1001, 1100, 1111을 만들 수 있다.

그렇다면 자연수 n = 3일때는?

001, 111, 100을 만들 수 있다.

 

이제 이 숫자들을 정리해보자.

자연수 n개일 때 만들 수 있는 2진 수열의 갯수는?

1, 2, 3, 5 .....

 

여기서 규칙을 찾을 수가 있는데, 3이라는 숫자는 앞의 두 수를 더한 (1+2) 결과값 이고, 5라는 숫자도 마찬가지로 앞의 두 수를 더한 (2+3) 결과값이다.

그럼 n = 5일 때는 3+5를 더한 결과값인 8이 될 것이다.

 

정리를 해보면 이 규칙이 피보나치 수열이라는 것을 알 수가 있다.

이제 리스트를 하나 만들어서, 이 수들을 넣어보자.

 

n = int(input())            # n = 7

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

0이 1000001개가 있는 리스트를 하나 만들어 준다.

0을 1,000,001개를 만들어 준 이유는, 문제에서 자연수 N은 1<= N <= 1,000,000 즉, 1이상 1백만이하라고 범위를 지정해줬기 때문이다.

 

1백만 개를 만들면 되는데, 1백만 + 1을 해준 이유는, 리스트에 0부터 넣어 놓을 것이기 때문이다.

위에서 찾아낸 규칙을 다시 한 번 살펴보면, 

 

dp[1] = 1

dp[2] = 2

dp[3] = 3

dp[4] = 5

 

여기에 dp[0] = 0을 만들어둬서 dp의 [인덱스 값]과 자연수 n의 값을 맞춰주기 위한 것이다.

만일, 0을 1,000,000개를 만들었다면?

예를 들어 dp = [1, 2, 3, 5, ]에서 자연수 n = 2일 때의 값을 꺼내려면 dp[n-1]이라고 해야 dp[1]의 값인 '2'를 꺼낼 수가 있다. 인덱스 계산하는 게 더 복잡해지고 머리 아파진다. +1해서 인덱스를 맞춰놓자. 

 

dp[1] = 1

dp[2] = 2

첫번째 값과, 두번째 값을 선언해주고, 이제 for문을 이용하러 가보자.

for i in range(3, n+1):     # i = 3, 4, 5, 6, 7
    dp[i] = (dp[i-1] + dp[i-2])

print(dp[n])

여기서는 n = 7 이라고 입력 받았다고 가정해보자.

i의 범위는 range(3, 8) 이니까, i는 3, 4, 5, 6, 7이다.

그리고 위에서 피보나치 수열에 대해 알아봤으니, 이걸 다시 한번 정리해보자.

 

dp[3] = dp[3-1] + dp[3-2]
dp[3] = dp[2] + dp[1] == 3

dp[4] = dp[3] + dp[2] == 5

자연수 n이 주어지고 dp[n]번째의 결과값을 얻으려면 dp[n] = dp[n-1] + dp[n-2] 라는 식을 만들 수 있다.

 

이처럼 n = 7이라면 for문을 돌면서 이런 과정이 만들어진다.

 

dp[3] = dp[2] + dp[1]  == 3
dp[4] = dp[3] + dp[2]  == 5
dp[5] = dp[4] + dp[3]  == 8
dp[6] = dp[5] + dp[4]  == 13
dp[7] = dp[6] + dp[5]  == 21

 

마지막으로 dp[7]을 출력해주면 되는데, 여기선 n값을 input()받았으니까 dp[n]으로 바꿔주면 된다.

 

여기까지 하고, 문제 제출을 하니 '메모리초과'가 떴다.

 

???왜

문제를 다시 한번 잘 읽어보자.

출력 부분을 보면, '2진 수열의 개수를 15746으로 나눈 나머지를 출력'하라고 나와있다.

다시 코드를 고쳐보면, 최종 코드는 아래와 같다.

n = int(input())            # n = 7

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3, n+1):     # i = 3, 4, 5, 6, 7
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[n])

왜 메모리 초과가 나오는 건지 구글링 해보니, 출력이 너무 커서 15746으로 나눈 나머지 값을 출력하는 거라고 하는데, 왜 숫자 15746으로 나누는 건지는 모르겠으나 dp[7]인 21 % 15746을 해보니 정말 나머지가 21이 나왔다.

문제에서 하라는대로 하고 제출 하니 정답 처리가 됐다.