[동적 계획법 1] [Python] 1904번. 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

 

 

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

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

---

해결 방법

언뜻보면 어려워 보일 수 있다. 하지만 타일의 경우의 수에는 규칙이 있다.

N	1	2	3	4	5	6	7
2진 수열의 경우의 수	1	2	3	5	8	13	21

피보나치와 같은 점화식을 가진다. f(n) = f(n-1) + f(n-2)

하지만 주의할 점이 시간 제한이 0.75초에 256MB의 메모리라는 점이다.

재귀를 사용하면 절대 통과할 수 없는 문제라는 뜻이다.

 

 

해결 과정

나는 첫번째 시도에서 메모리 초과가 나왔었다.

dp로 구현했기에 무조건 통과라고 생각했는데 메모리 초과가 나와서 당황했다.

 

문제를 다시 살펴본 결과

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

이게 핵심이었다.

dp 배열에 15746으로 나눈 나머지를 넣어줌으로써 15745 이하의 값들만 이용하고 이 과정으로 연산 과정에서 메모리 소모를 줄이는 것이었다.

 

'%15746' 코드를 추가하였더니 바로 통과하였다.

 

최종 코드는 

 

def main():
    n = int(input())
    
    number = [0]*1000001
    
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    else:
        number[1] = 1
        number[2] = 2
        for i in range(3, n+1):
            number[i] = (number[i-1] + number[i-2])%15746
        print(number[n])
        
if __name__ == "__main__":
    main()