[백준] N으로 만들기

최동혁·2022년 12월 6일

baekjoon python 알고리즘

백준

목록 보기

63/68

N으로 만들기

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

521을 만드는 방법은 다음과 같이 4가지이다.

1 → 21 → 521
2 → 21 → 521
2 → 52 → 521
5 → 52 → 521

예제 출력 1

예제 입력 2

9111을 만드는 방법은 다음과 같이 4가지이다.

1 → 11 → 111 → 9111
1 → 11 → 911 → 9111
1 → 91 → 911 → 9111
9 → 91 → 911 → 9111

예제 출력 2

문제 해석

이어져 있는 숫자들을 조합해서 만드는 경우의 수를 출력해주는 문제이다.
트리를 생각하면 편하다.
왼쪽 가장자리에 있는 수는 이어져있는 숫자가 1개있고, 오른쪽 가장자리도 마찬가지이다.
그 외의 숫자들은 왼쪽, 오른쪽 각 하나씩 이어져 있어서 트리의 성질과 비슷하다.
깊이 탐색을 하면서 이어져있는 문자들끼리 완성을 해가면서 완성이 되었으면 ans에 넣어준다.

풀이

dfs 선언
- sum의 0번지에 있는 값과 같으면 끝남.
- 왼쪽이 있는 경우
  - dfs 재귀 호출
  - 전에 문자열이 만들어진 경로 string과 그 string에 왼쪽에 문자열을 붙여줘야 하기 때문에 왼쪽에 붙인 string을 더해준다.
  - 왜 이렇게 해주냐면
```
101에 예외가 있다.
101이 만들어지는 순서
```
  1. 1 -> 10 -> 101
  2. 0 -> 10 -> 101
  3. 0 -> 01 -> 101
  4. 1 -> 01 -> 101
  - 이렇게 4가지가 있다.
  - 하지만 숫자가 이어붙이는 순서대로만 string에 더해준다면?
  1. 1 10 101 = 101
  2. 0 10 101 = 011
  3. 0 01 101 = 011
  4. 1 01 101 = 101
  - 이렇게 되어서 중복 제거를 해주면 2가지가 된다.
  - 뒤에 숫자 101, 011, 011, 101은 숫자가 붙게된 순서대로 써준 것이다.
  - 1이라는 중복되는 숫자가 있기 때문에 중복 체크를 제대로 못하게 된다.
  - 그래서 문자열들이 붙어가는 경로들을 전부다 string에 넣어주면 중복되는 숫자들이 있더라도 다른 경로로 만들어진 숫자를 판별해준다.
  1. 1 10 101 = 101 -> 1 -> 110 -> 1101101
  2. 0 10 101 = 011 -> 0 -> 010 -> 0100101
  3. 0 01 101 = 011 -> 0 -> 001 -> 0010011
  4. 1 01 101 = 101 -> 1 -> 101 -> 1011011
  - 그래서 왼쪽 노드가 있으면
  - string + N[left - 1] + string
- 오른쪽 노드가 있으면
  - string + string + N[right + 1]
- 이런식으로 왼쪽 노드 호출 후 오른쪽 노드 호출을 해준다.

import sys

N = sys.stdin.readline().rstrip()

ans = []
sum = [0]
for _ in range(len(N)):
    sum[0] = sum[0] * 2 + 1

def dfs(left, right, string):
    if len(string) == sum[0]:
        ans.append(string)
    if left > 0:
        dfs(left - 1, right, string + N[left - 1] + string)
    if right < len(N) - 1:
        dfs(left, right + 1, string + string + N[right + 1])
        
for i in range(len(N)):
    dfs(i, i, N[i])
print((len(set(ans))))