[알고리즘] 백준 14650 파이썬 - 걷다보니 신천역 삼 (Small)

 

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

 

문제

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

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

 

문제풀이

N=int(input())
ans=0
#01
def dfs(n,sum):
    global ans
    for i in range(3):
        if n==0 and i==0:
            continue
        if n==N:
            if sum%3==0:
                ans+=1
                return ans
        else:
        	#02
            dfs(n+1,sum+i)
#03
dfs(0,0)
print(ans)

- #01 : 처음 시작값이 0이고, i도 0이면 continue한다. 만약 n값이 처음 입력받는 N값과 같다면

           sum의 값이 3의 배수가 맞다면 ans에 1을 더하고 return ans를 한다.

- #02 : 그렇지 않다면 dfs의 n값에 1을 더하고 sum값에 i를 더해 재귀한다.

- #03 : 함수의 시작은 0,0부터 시작한다.

           결과적으로 얻은 ans를 출력한다.

위와 같이 2를 입력했을 때 재귀함수는 (0,0) - (1,1) - (2,1) - (2,2) - (2,3) -> ans+=1 후 return

                                                                         (1,2) - (2,2) - (2,3) -> ans+=1 후 return 

참고로  3의 배수는 각 자리의 합이 3의 배수이기에 sum%3==0으로 3의 배수를 구할 수 있다.