[파이썬/python] 백준 - 14651 걷다보니 신천역 삼 (Large)

문제

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

---

문제 설명

1. 3개의 숫자(0,1,2)만 가지고 N자리 3의 배수를 만든다.
2. N자리로 만들 수 있는 배수의 개수를 구한다.

 

---

풀이

(0,1,2) 세 가지 숫자로 만들어지는 숫자는 3으로 나누었을 때 나머지가 0,1,2만 나오게 된다.

따라서 나머지가 동일한 숫자 별로 나누어서 보면, 규칙을 찾을 수 있다.

간단하게 예시를 들어보자.

 

나머지	0	1	2
N = 2	12, 21	10, 22	11, 20
N = 3	120, 210, 102, 222, 111, 201	,,,	,,,

N = 2일 때 나오는 각 나머지 별 숫자의 개수는 2개이다. 결국에는 뒤에 숫자가 돌림이 되기 때문에 각 나머지 별 숫자는 동일하게 생성된다. 여기서 우리가 알아야 할 정보는 나머지가 0인 수(3의 배수)이다.

N = 3일 때 나머지가 0인 숫자를 보면 N = 2일 때 나온 수에 0,1,2를 붙인 수 이다. 결국에는 이전에 나온 수에 맞게 0,1,2를 붙이게 되면 무조건 나머지를 0으로 만들 수 있게 된다.

즉 N = a일 때 A개라면, N = a+1일 때 3*A개이다.

이를 일반화 해보게 되면,

$N = 2$일 때    $2$개

$N = 3$일 때    $2*3$개

$N = 4$일 때   $2*3*3$개

... 

$N = A$일 때 $2*3^{N-2}$개

즉 정답은 $2*3^{N-2}$으로 일반화가 가능하다.

 

1. $2*3^{N-2}%MOD$을 출력한다.

---

코드

import sys
input = sys.stdin.readline

MOD = 1000000009
N = int(input())
if N == 1:
    print(0)
    exit()
print(2*3**(N-2)%MOD)

---

시간복잡도

• 단순 수식으로 계산되기 때문에 $O(1)$이다.