문제 설명

이번 포스팅은 백준 17255번: N으로 만들기 문제 풀이에 대한 기록입니다.

문제를 간단히 요약해보면, "음이 아닌 정수 N이 주어지면, N을 이루는 숫자 중 한 숫자로 시작해서 양쪽에 숫자를 붙여가며 N을 만드는 방법의 개수를 출력하는 문제" 입니다.

이 문제에서 한 가지 주의할 점은, "숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다." 라는 점입니다.

ex) N으로 "119"가 주어진 경우

i) 맨 앞 1로 시작 : 1 $\to$ 11 $\to$ 119
ii) 중간 1로 시작 : 1 $\to$ 11 $\to$ 119

위의 두 가지 케이스는 숫자를 적는 과정에서 나온 수가 순서대로 1, 11, 119 이므로 같은 방법으로 생각한다는 뜻입니다.

저는 저 주의사항을 "숫자를 적는 과정에서 앞 or 뒤에 새로 붙이는 숫자가 순서대로 모두 같다면 같은 방법이다"로 이해하고 많은 시간을 낭비했더랬죠ㅠㅠ 문제를 먼저 제대로 이해하고 접근하는 것이 제일 중요한 것 같습니다.

풀이

앞, 뒤에 숫자를 하나씩 추가할 때마다 맨 앞, 뒤를 기록하며 나아가기

---

새로운 숫자는 현재 숫자의 앞 or 뒤에 추가할 수 있습니다.

그러나 앞 or 뒤에 아무 숫자나 추가하는 것은 아닙니다. 우리는 만들고자 목표로 하는 숫자 N이 있기에, 결과적으로 N을 만들기 위해선 매 단계마다 앞 or 뒤에 추가해야하는 딱 정해진 숫자가 있습니다.

여기서 추가해야하는 딱 정해진 숫자는 목표 숫자 N을 보면 알 수 있겠죠.

따라서, 현재 상태의 맨 앞, 맨 뒤 숫자가 목표 숫자에서 어느 위치에 있는지를 보고 그 다음에 위치한 숫자를 추가 해나가면 됩니다.

위에서 예로 들었던 "119"를 만드는 과정으로 설명하자면,

1. 맨 앞 1로 시작하는 경우,
   
   
   • index=0에 위치한 1로 시작 -> 1
   • 왼쪽에는 숫자가 더 없으므로, 한 칸 오른쪽의 index=1인 1을 추가 -> 11
   • 다시 한 칸 오른쪽 index=2인 9를 추가 -> 119
     
     
2. 중간 1로 시작하는 경우,
   
   
   • index=1에 위치한 1로 시작 -> 1
   • 두 갈래로 나뉨
     i) 한 칸 왼쪽 index=0인 1을 추가 -> 11
       - 왼쪽에는 숫자가 더 없으므로, 한 칸 오른쪽의 index=2인 9을 추가 -> 119
     ii) 한 칸 오른쪽 index=2인 9를 추가 -> 19
       - 오른쪽에는 숫자가 더 없으므로, 한 칸 왼쪽의 index=0인 1을 추가 -> 119

이를 위해선 새로 숫자를 추가할 때마다 맨 앞과 맨 뒤 숫자의 위치를 기록할 필요가 있습니다.

def solution(case, left, right, seque):
    if case == N and seque not in visited:
        visited[seque] = 0
        global answer
        answer += 1

    else:
        if left > 0:
            solution(nums[left-1]+case, left-1, right, seque+case)  

        if right < len(nums)-1:
            solution(case+nums[right+1], left, right+1, seque+case)

위 함수에서 left, right가 의미하는 것이 바로 N을 기준으로, 현재 상태(case)의 맨 앞, 뒤 숫자가 위치하는 index입니다.

일단 else문 내부를 보겠습니다.

nums 배열은 목표 숫자 N이 한 자리씩 떨어져 저장되어 있는 배열입니다.

left > 0, 즉 아직 앞쪽에 붙일 숫자가 남았다면 nums에서 한 칸 앞쪽 숫자를 새로 붙이고 left-1을 하여 넘깁니다.

seque는 현재까지 오면서 나온 숫자들을 이어붙인 문자열입니다. 현재 상태를 seque에 이어붙인 후 다음 단계로 넘깁니다.

right < len(nums)-1, 똑같이 뒤쪽에 붙일 숫자가 남았다면 nums에서 한 칸 뒤쪽 숫자를 새로 붙이고 right+1, seque을 갱신하고 넘깁니다.

dictionary를 이용하여 빠른 중복 확인

---

python의 dictionary를 이용하여 중복여부를 빠르게 검사할 수 있습니다.

dictionary에 저장된 데이터는 key: value 형태로 저장되어, 데이터를 조회할 때 앞에서부터 순차적으로 접근하는 것이 아니라 key로 바로 조회가 가능하기 때문에 시간복잡도가 $O(1)$인 것이 특징입니다.

중복여부는 해당 데이터를 조회해보면 알 수 있으니까 $O(1)$이겠죠?

if case == N and seque not in visited:
	visited[seque] = 0	# visited: seque들이 저장된 dictionary
	global answer	# 정답을 기록하는 전역변수
	answer += 1

위처럼 case가 목표에 도달하면, 그 과정을 기록한 seque이 중복이 아닐때만 seque를 dictionary인 visited에 새로 추가, 정답에 +1을 하면 되겠습니다.

for i in range(len(nums)):
    solution(nums[i], i, i, nums[i])

처음 시작할 때는 위와 같이 N을 구성하는 숫자들을 하나씩 차례로 넘기며 시작하면 됩니다.

문제 해결!!

결과 코드

N = input()

nums = list(N)
visited = dict()
answer = 0

def solution(case, left, right, seque):
    if case == N and seque not in visited:
        visited[seque] = 0
        global answer
        answer += 1

    else:
        if left > 0:
            solution(nums[left-1]+case, left-1, right, seque+case)  
            
        if right < len(nums)-1:
            solution(case+nums[right+1], left, right+1, seque+case) 

for i in range(len(nums)):
    solution(nums[i], i, i, nums[i])
    
print(answer)