[Python] 백준/BOJ 14650번: 걷다보니 신천역 삼 (Small) (Silver 2)

💻 Problem

문제 보러 가기

 

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

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

• N을 입력 받으삼. (1 ≤ N ≤ 9)

 

💡 Approach

중복 순열로 N자리 수를 뽑은 다음 0으로 시작하지 않는 3의 배수이면 횟수를 센다.

사실 파이썬 itertools 모듈은 순열(permutations), 조합(combinations)만 알고 있었는데

이번에 중복 순열(product)과 중복 조합(combinations_with_replacement)도 알게 되었다.

기억할 점은 다른 건 다 인자가 (리스트, 뽑을 개수)지만 중복 순열은 (리스트, repeat=뽑을 개수)이다.

 

✏️ Solution

import sys
from itertools import product
input = sys.stdin.readline

N = int(input())
num = ['0', '1', '2']
cnt = 0

for p in product(num, repeat=N):
    if p[0] == '0':
        continue
    if int(''.join(p)) % 3 == 0:
        cnt += 1

print(cnt)

중복 순열의 시간복잡도는 3^N이다.

N의 최댓값이 9이므로 대입하면 3^9 = 19,683이다.