[Python] 백준/BOJ 14651번: 걷다보니 신천역 삼 (Large) (Silver 1)

💻 Problem

문제 보러 가기

 

욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼.

3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼?

• N을 입력 받으삼 (1 ≤ N ≤ 33,333)

 

💡 Approach

걷다보니 신천역 삼 문제는 Small이 있고 Large가 있다.

• Small 문제 풀이

Small 보다 Large가 입력 범위가 훨씬 커서 중복 순열로 풀면 시간 초과가 뜬다.

 

중복 순열 코드에 입력을 순서대로 넣어봤더니 이런 결과가 나왔다.

입력	출력
1	0
2	2
3	6
4	18
5	54
6	162

...

 

위 표를 보니 2에 3을 곱하면 6, 6에 3을 곱하면 18, 18에 3을 곱하면 54, 54에 3을 곱하면 162, ... 였다!

오 그냥 3만 계속 곱해주면 되네??

 

그냥 반복문으로 N-2만큼 3을 곱하도록 하였다.

 

✏️ Solution

import sys
input = sys.stdin.readline

def solve():
    if N == 1:
        return 0
    
    cnt = 2
    for _ in range(N - 2):
        cnt *= 3
    return cnt % (10 ** 9 + 9)

N = int(input())
[print(solve())]

반복문으로 N-2만큼 3을 곱해서 푼 코드이다.

 

import sys
input = sys.stdin.readline

N = int(input())
print(int(2 * 3 ** (N - 2)) % 1_000_000_009)

이렇게 더 짧게 구현할 수도 있다.

3을 N-2만큼 곱했다는 건 3^(N-2)라는 의미니까.