[Python/파이썬] 백준 17255번 N으로 만들기

17255번: N으로 만들기

 

문제

준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.

처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.

다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.

1. 수의 왼쪽에 숫자를 하나 적는다.
2. 수의 오른쪽에 숫자를 하나 적는다.

준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다.

단, 숫자를 적는 과정에서 수는 0으로 시작할 수 있다.

입력

음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000)

출력

N을 만드는 방법의 수를 출력한다.

코드

from collections import defaultdict

n = input()
chars = defaultdict(int)
for i in list(n):
    chars[i] += 1

ans = 0
methods = []


def bt(x, path):
    global ans
    if len(x) == len(n):
        if x == n:
            ans += 1
        return
    for c, num in chars.items():
        if num == 0:
            continue
        # 양옆에 붙이기
        for nx in [c+x, x+c]:
            if n.find(nx) > -1 and path+[nx] not in methods:
                chars[c] -= 1
                methods.append(path+[nx])
                bt(nx, path+[nx])
                chars[c] += 1


bt('', [])
print(ans)

 

우선 주어진 n에 들어가는 숫자의 종류와 개수를 파악해서 chars에 저장해주고 이것들을 갖고 백트래킹을 수행한다.

백트래킹

• 파라미터로 받는 문자열 x는 이제까지 만들어진 수이다.
• chars의 원소들 중 사용 가능한 숫자의 개수를 의미하는 value가 0이 되지 않은 원소들을 x의 양옆에 붙여본다.
  • 이때 양옆에 붙인 결과물 nx가 n에 존재하지 않는 문자열이거나 이미 만들어졌던 순서이면 더이상 만들지 않는다.
    예를 들어, n이 9111일때 nx로 19가 만들어지면 이것을 가지고는 9111을 만들 수 없기 때문에 더이상 진행하지 않는다. 그리고 1->11이 이미 만들어진 적 있는데 또 1->11이 나온다면 이 역시도 더이상 진행하지 않는다.
  • 아직 만들어진 적 없는 순서로 만들어졌고, n에 존재하는 문자열 nx라면 이번에 사용한 숫자의 개수를 chars에서 1 감소시켜주고, 이제까지 만들어진 순서를 저장하는 methods에 nx까지 포함된 순서를 저장한다.
    그리고 bt를 재귀호출한다.
• 만약 x의 길이가 n의 길이와 같아진다면 리턴할것인데, x==n이라면 우리가 원하는 n을 만들 수 있는 방법이므로 이대 전역변수 ans의 값을 1 증가시켜준다.