[백준/BOJ/1904] 01타일

movie·2021년 11월 1일

1904 | 01타일

문제 접근 & 설계

타일은 00, 1이 존재
크기가 N인 2진 수열 만들기
2진 수열의 개수를 15746으로 나눈 나머지를 출력

N = 1 --> 1
N = 2 --> 00, 11
N = 3 --> 001, 100, 111

시간 제한이 짧기 때문에 무조건 DP로 풀어야 하겠다고 생각했다.

사용한 스킬

시간 복잡도

for : O(n)

total o(n)

개선

처음에는 배열을 저장해서 다음 배열을 구할 때 사용하면 시간이 줄겠다.. 라고 생각했다.
장렬하게 시간초과

import sys

def count(n):
    arr = [['1'], ['00', '11']]

    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        base = 2

        while base < n:
            cur = set()

            for a in arr[base - 2]:
                cur.add(a + '00')
                cur.add('00' + a)
            for a in arr[base - 1]:
                cur.add(a + '1')
                cur.add('1' + a)

            arr.append(list(cur))
            base += 1

    print(arr[-1])

    return len(arr[-1])

이 코드를 짜기까지의 나의 생각은

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

위와 같이 수열이 이루어지므로 만약 N = 5를 구하려면 N = 3의 수열에는 00을 앞뒤에 붙이고 N = 4의 수열에는 1를 앞뒤에 붙이면 될 것이라고 생각했다.
앞뒤에 붙여야한다고 생각한 이유는
- 만약 N = 5라고 하자, XXXXX 5칸이 존재할 때 N = 3 수열을 활용하면 3칸의 경우의 수는 N = 3에서 모두 구해져있는 상태이다. 3칸을 제외한 숫자가 존재할 수 있는 공간은 0은 00이 붙어 움직여야 하므로 앞과 뒤밖에 없다. 1의 경우도 마찬가지이므로 앞뒤 밖에 없다.
하지만 여기서 문제인게 앞과 뒤 모두를 고려하면 중복이 생긴다는 것이다.
- 중복을 없애기 위해서 set()을 사용했다.
이 로직으로 짠 코드가 바로 위의 코드이고 이는 시간초과가 발생한다.
- 직접 배열을 만드는 과정이 오래걸린 듯 하다.

이후 질문글을 살며시 봤고
이 문제는 피보나치 수열을 사용해야 시간초과가 나지 않는다는 사실을 알아냈다..!

위 수열을 보면 피보나치 수열인 것을 알 수가 있다.
근데 왜 피보나치 수열이 될까?

내 전 풀이를 참고하면 앞 뒤에 00과 1을 추가했기 때문에 중복이 발생했다. 이를 set()으로 해결했고, 애초에 00과 1을 앞이나 뒤에만 추가면 중복이 안생긴다.
만약 앞에나 뒤에만 00과 1을 추가했다고 치면 결국 N-2배열과 N-1배열의 크기를 합친게 답이 된다. 그래서 피보나치 수열이였던 것..

import sys

countList = [0, 1, 2]

def countTile(n):
    for i in range(3, n + 1):
        countList.append((countList[i - 2] + countList[i - 1]) % 15746)

    print(countList[n])

N = int(sys.stdin.readline())

countTile(N)

시간초과를 해결하니 이번엔 메모리초과가 나왔다.. (🌋넘어 🌋)
왜 메모리 초과인가.. 또 질문을 살며시 봤다.
- 이건 문제에 나와있는 힌트이다.

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

아니 왜 뜬금없이 15746으로 나누나했더니 파이썬은 동적으로 int형을 할당하기 때문에 수가 매우 커지면 더 큰 메모리를 할당 받게 되고 이 때문에 메모리 초과가 난다는 것이였다.
- 여기까지는 이해할 수 있었다. 큰 수를 줄이기 위해 mod 연산을 하라는 건데 mod 연산을 한 이후로도 피보나치 수열이 유지되는지가 의문이였다.