[Python/파이썬] 백준 14650번 걷다보니 신천역 삼 (Small)

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

코드

n = int(input())

answer = 0


def bt(n, chosen):
    global answer
    if len(chosen) == n:
        if sum(chosen) % 3 == 0:
            answer += 1
        return

    start = 1 if len(chosen) == 0 else 0
    for i in range(start, 3):
        bt(n, chosen+[i])


bt(n, [])
print(answer)

 

3의 배수는 각 자릿수의 합이 3의 배수라는 것은 수학적 사실이다. 이러한 수학적 사실과 백트래킹 알고리즘을 사용하여 풀었다.

 

0,1,2 중 N개의 숫자를 중복순열로 만드는 방법을 백트래킹으로 구현했다. 이때, 주의할 점은 첫번째 자리는 0이 올 수 없기 때문에 `start = 1 if len(chosen) == 0 else 0` 0번째 자리의 수는 for문이 1부터 돌도록 했다.