[Baekjoon]백준 1904 01타일(실버 3) - Python

문제설명

문제를 살펴보면 0을 하나만 사용해서는 타일을 만들수없으며 00 또는 1로만 타일을 만들 수 있는 가짓수를 구해야한다

그리고 이를 15746으로 나눈 값을 출력하면 된다

 

처음에 들었던 생각은 재귀 함수를 이용하면 제일 간단하게 해결이 가능하지 않을까? 라는 생각이었다

그래서 함수에 seq를 받아 길이가 N-2보다 작은 경우와 N-1보다 작은 경우로 나누어 문자열에 더해주었다

그대로 제출하게 되면 런타임 에러 (RecursionError)가 발생한다

def make_seq(seq):
    if len(seq) == N:
        result.append(seq)
        return
    if len(seq) <= N-2:
        make_seq(seq + '00')
        
    if len(seq) <= N-1:
        make_seq(seq + '1')

N = int(input())
seq = ''
result = []
make_seq(seq)
print(len(result) % 15746)

그러고나서 아차 싶었다 지금 풀고있는 문제의 단계는 동적 계획법이다

이 문제를 해결할 수 있는 훨씬 간단한 방법이 있음을 깨닫고 규칙을 찾아보니

N = 1일때 1, → ['1']

N = 2일때 2, → ['00', '11']

N = 3일때 3, → ['001', '100', '111']

N = 4일때 5, → ['0000', '0011', '1001', '1100', '1111']

N = 5일때 8.... → ['00001', '00100', '00111', '10000', '10011', '11001', '11100', '11111']

과 같은 피보나치 수열과 같은 규칙이 발생한다 

이 규칙을 활용하여 코드를 작성하면 밑의 코드가 된다

N = int(input())
result = [0, 1, 2]

for i in range(3, N+1):
    result.append(result[i-1] + result[i-2])

print(result[N] % 15746)

이대로 제출하면 되는줄 알았더니 메모리 초과가 발생한다

분명 Python3는 int형에 오버플로우가 없는거로 알고있는데 메모리 초과가 발생한다

찾아보니 주어진  n의 값이 1,000,00이기 때문에 중간에 15746을 나누어주어야 int형의 범위를 넘어가지 않는다고 한다

흠...자세한 이유는 추후에 찾으면 업데이트 하도록 하겠다

→ Python은 큰 수를 다룰 수 있지만, 그로 인해 메모리 사용량이 증가하기 때문에 메모리 초과가 발생하는 것

제출을 위해 5번째 줄에 % 15746을 더하여 코드를 제출하면 정답임을 확인할 수 있다

N = int(input())
result = [0, 1, 2]

for i in range(3, N+1):
    result.append((result[i-1] + result[i-2]) % 15746)

print(result[N] % 15746)