[Python] 백준 14651번 문제, 걷다보니 신척역 삼(Large)

<문제 링크>

 

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

14651번: 걷다보니 신천역 삼 (Large)

 

---

<풀이>

 

1부터 N자리까지의 1, 2, 0으로 구성된 3의 배수를 하나씩 구한다면, 실행 시간이 너무 길어 시간 초과가 뜰 것이다.

 

하나씩 다 구하면 시간 초과가 발생하기 때문에 뭔가 수학적 규칙을 찾아야한다.

수학적 규칙을 찾기 위해 조건에 맞는 낮은 자릿수를 직접 적어보자.

 

N	Result
1	0
2	2
3	6
4	18
5	54

 

이렇게 누적합이 생기는데 N자릿수의 값은 (N-1자릿수 값 * 3)인 걸 확인 할 수 있다.

또한, 출력 형식에 맞추기 위해 1,000,000,009로 나눴을 때의 나머지를 dp[]에 넣어주면 된다.

 

---

<코드>

dp[]: 1, 2, 0으로 구성되어 있는 3의 배수 누적합 리스트

---

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    dp = [0 for _ in range(N+1)]

    if N >= 2:
        dp[2] = 2
        for i in range(3, N+1):
            dp[i] = (dp[i-1] * 3) % 1000000009

    print(dp[N])