백준 17255 - N으로 만들기 (파이썬)

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

풀이

문제의 핵심은 주어진 숫자 N을 만들 수 있는 가능한 순서열을 모두 찾아 그 개수를 세는 것이다.

여기서는 재귀적 브루트포스 기법을 활용하여 주어진 숫자 N을 만들 수 있는 모든 경우를 탐색하는 방식을 사용한다.

재귀 함수를 구현하였고, 해당 재귀함수의 기능은 다음과 같다.

1. n이 현재까지 만들어진 숫자 문자열
2. N을 만들수 있는 모든 방법을 재귀적으로 탐색한다.
3. n == N 을 통해서 현재 n이 N과 같다면 하나의 유효한 방법을 찾은 것이므로 1을 반환한다.
4. N.find(n) == -1 을 통해서 n이 N에 포함되지 않는 부분 문자열이면 더 탐색할 필요가 없기에 0을 반환한다.
5. n의 앞 또는 뒤에 숫자 i(0~9)를 추가한 left와 right을 만든다.
   1. 예를 들어 n="2"인 경우
      1. left = "02" (왼쪽 추가)
      2. right = "20" (오른쪽 추가)
   2. left == right인 경우 중복 호출을 방지하여 한 번만 재귀 호출.
   3. 그렇지 않다면 좌우 각각 재귀적으로 호출.

코드

# 백준 17255 - N으로 만들기
# 분류 : 브루트포스

N = input()

def f(n) :
    if n == N :
        return 1
    
    if N.find(n) == -1 :
        return 0
    
    ret = 0
    for i in range(10) :
        left = str(i) + n
        right = n + str(i)

        if left == right :
            ret += f(left)
        else :
            ret += f(left)
            ret += f(right)

    return ret

answer = 0
for i in range(10) :
    answer += f(str(i))

print(answer)