[백준/python] 14650:걷다보니 신천역 삼(small)

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

14650번: 걷다보니 신천역 삼 (Small)

 

import sys
input=sys.stdin.readline
n=int(input())
se=[0,1,2]
s=[]
t=[]

def Bfs(arr):
    if len(arr)==n:
        k=0

        for i in range(n):

            k+=arr[i]*(10**(n-i-1))

        t.append(k)
    
        return

    for i in se:    

        arr.append(i)

        Bfs(arr)

        arr.pop()


Bfs(s)

sum1=0
for k in t:
    
    if k%3==0 and len(str(k))==n:
        if k!=0:
            
            sum1+=1
print(sum1)

풀이가 되는 아이디어를 떠올리느냐가 중요했다.

0,1,2만 가지고 수를 만드릭로 했으므로 리스트에 0,1,2를만들고

순열을 만들때처럼 리스트 내부에 쓰일 리스트를 만들어 길이가 조건을 만족시키면

리스트 요소를 각각 자릿수를 곱해서 k에 더해준후 

나중에 3의배수인지를 판단할 리스트에 넣어준후

3으로 나누었을때 나머지가 없고 0으로 시작하는 것을 방지하기 위해 길이가 n인지 체크해서 개수를 구하면 되었다. 

문제푸는데 걸리는 시간을 줄이는게 매우 시급하다