[BOJ/python] 14651번 걷다보니 신천역 삼 (Large)

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

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

문제 해석
(0, 1, 2 로 만든 N자리 숫자 중에서 3의 배수의 개수)를 1000000009로 나눈 나머지를 출력한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())

if n == 1:
    print(0)
else:
    result = (3 ** (n - 2)) * 2
    print(result % 1000000009)

---

문제 풀이

수학적인 원리가 아닌 규칙을 통해 설명하겠다.

 

N = 1일 때에는 0, 1, 2이므로 존재하지 않는다.

N = 2일 때의 경우의 수는 2*3 = 6가지, 그 중 3의 배수는 12와 21로 2개이다.

N = 3일 때의 경우의 수는 2*3*3 = 18가지, 그 중 3의 배수는 6개이다.

 

여기서 우리는 N자리에서의 경우의 수는 2(3**(N-1)), 3의 배수는 2(3**(N-2))를 알 수 있다.

따라서 구하고자 하는 값은 2(3**(N-2))이며, 이를 1000000009로 나누어 주면 된다.

(참고로 N >=19 이면 1000000009를 넘기게 된다.)