[백준] 15990번 (python 파이썬)

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

 

import sys
testcase = int(input())

cache = [[0 for _ in range(4)] for i in range(100001)]
cache[1] = [0,1,0,0]
cache[2] = [0,0,1,0]
cache[3] = [0,1,1,1]
for i in range(4, 100001):
  cache[i][1] = (cache[i-1][2] + cache[i-1][3])
  cache[i][2] = (cache[i-2][1] + cache[i-2][3])
  cache[i][3] = (cache[i-3][1] + cache[i-3][2])
  
for _ in range(testcase):
  n=int(sys.stdin.readline())
  print(sum(cache[n]) % 1000000009)

 

미리 최대로 계산을 해놓고 입력 받는 수에 따라 계산된 값을 출력하도록 하였다.

그런데 시간초과가 된다.

 

이는 저 위 코드상 편의를 위해 cache[1]의 길이를 4개로 설정했기 때문이 아니다. 3개로 해도 시간초과가 난다.

예상 못했지만, cache[100000][1]의 계산 결과는

 

14735042208788136442688965299010550778944029140074411521888409346269339148668211909477951607915246

596475808048820350391355732...

 

라고 한다. ... 이후에 엄청 많은 수가 생략 되어있다. 이러니까 계산시 시간초과가 나지...

 

여기서 사용할 방법은 모듈러 연산이다.

모듈러 연산은 다음의 특징을 가진다.

 

모듈러 연산자 특성

1. [(a mod n)+(b mod n)] mod n = (a+b) mod n

 

2. [(a mod n)*(b mod n)] mod n = (a*b) mod n

 

sum(cache[n]) mod N 은 (cache[1] + cache[2] + cache[3]) mod N이 된다.

 

(cache[1] + cache[2] + cache[3]) mod N = (cache[1] mod N + cache[2] mod N + cache[3] mod N) mod N 

 

위의 특성을 이용해 다시금 코드를 작성하면

import sys
testcase = int(input())

cache = [[0 for _ in range(4)] for i in range(100001)]
cache[1] = [0,1,0,0]
cache[2] = [0,0,1,0]
cache[3] = [0,1,1,1]
for i in range(4, 100001):
  cache[i][1] = (cache[i-1][2] % 1000000009 + cache[i-1][3] % 1000000009) % 1000000009
  cache[i][2] = (cache[i-2][1] % 1000000009 + cache[i-2][3] % 1000000009) % 1000000009
  cache[i][3] = (cache[i-3][1] % 1000000009 + cache[i-3][2] % 1000000009) % 1000000009
  
for _ in range(testcase):
  n=int(sys.stdin.readline())
  print(sum(cache[n]) % 1000000009)

 

아 참고로 코드상에 처음 cache 리스트를 초기화 할때

cache = [[0 for _ in range(4)] for i in range(100001)]

대신

cache = [[0]] * 100001

로 하면 다른 결과값이 나온다.

이는 얕은 복사에 의한 것으로

cache[0]과 cache[1]과 cache[2] ... cache[10000] 은 같은 리스트를 가리키기 때문이다.