1309번 동물원

 

문제풀이

동적 프로그래밍의 문제들을 풀어보면서 동적 프로그래밍 문제들은 어느 조건들을 만족하면 답을 도출하기 쉽다는 것을 알았다. 이문제에서도 한가지 조건이 있었다.

N = 1 : 1 1개

N = 2 : 00 11 2개

N = 3 : 001 100 111 3개

N = 4:  0011 0000 1001 1100 1111 5개

인 것처럼 여기서 지금 값의 개수는 이전 값, 이전 값의 이전 값을 더하면 지금 값의 개수를 얻을 수 있다.

 

그리고 결과값으로 15746을 나누고 남은 나머지 값을 출력해야 한다. 그러나 최종값에서만 모듈러 연산을 해주게 되면 100만번까지 도는 코드에서 메모리 초과가 나기때문에 for문을 돌때 마다 15746을 나눈 나머지 값만 저장해서 최종값을 도출 한다.

import sys
N = int(sys.stdin.readline())
arr = [0 for _ in range(1000001)]
for i in range(1,N+1):
    if i == 1: arr[i] = 1
    elif i == 2: arr[i] = 2
    else: arr[i] = (arr[i-1] + arr[i-2]) % 15746
print(arr[N])

 

코드