🔢 N으로 만들기

30 Jul 2022 in Algorithm on Dfs, Backtracking

백준 Gold4

N으로 만들기

문제

---

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

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

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

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

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

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

입력

---

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

출력

---

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

예제 입력 1

521

예제 출력 1

4

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

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

예제 입력 2

9111

예제 출력 2

4

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

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

📖 가져다 쓰기

이전에 투포인터 알고리즘을 활용했던 문제가 생각나서 그렇게 접근해보려고 했지만 실패 …

왜냐하면 투포인터는 특정한 합을 갖는 부분 연속 수열을 구하는 알고리즘인 방면 이 문제는 부분 연속 적이지 않기 때문이다.

알고리즘 분류가 백트래킹으로 되어있어 이 문제가 왜 백트래킹인지 한참을 고민했지만 이해가 안 되어서 치욕적이게도 솔루션을 참고하였다.

백트래킹을 활용하는 유형이 굉장히 많겠지만 그 중 하나가 [문자열을 쌓거나 줄일 때] 사용한다.

📐 과정 설계/관리

일단 DFS 동작 과정은 아래에서 설명하고 전체적인 흐름을 먼저 짚어보겠다.

521을 만드는 과정 중에 5 ➡️ 52 ➡️ 521 을 우리는 552521로 표현할 것이다.

따라서 길이가 N인 숫자의 과정 길이는 N(N+1) / 2 가 된다. (등차수열의 합)

DFS를 통하여 구한 모든 과정을 집합에 넣고 (중복을 제거하기 위하여) 우리는 최종적으로 집합의 길이를 뽑아내면 된다.

5,2,1 중에서 2부터 시작하는 경우를 살펴보면 왼쪽부터 탐색을 진행하여 process 변수에 과정을 계속 기록해나간다.

그리고 왼쪽이 5까지 도달했으면 다시 오른쪽을 1까지 탐색한다.

그렇게 해서 첫번째 케이스 2 ➡️ 252 ➡️ 252521 이 만들어졌고 이 과정을 계속하여 반복한다.

2뿐만 아니라 5와 1에서 시작했을 경우도 동일하게 반복해주면 된다.

진행과정은 아래 그림과 같다.

👨🏻‍💻 CODE

import sys
input = sys.stdin.readline

num = input().rstrip()
length = len(num)*(len(num)+1) // 2
way = set()

def dfs(left,right,process):
    if len(process) == length:
        way.add(process)
        return
    
    if left > 0:
        dfs(left-1,right,process+num[left-1:right+1])
    
    if right < len(num):
        dfs(left,right+1,process+num[left:right+2])
    
for i in range(len(num)):
    dfs(i,i,num[i])

print(len(way))