[백준][Python] 17255 N으로 만들기

기본적으로 문자열을 쌓거나 줄이는 방법은 dfs가 기본이다.

 

1번풀이 : 하나씩 쌓는 방법

left, right로 하나씩 쌓아가며 이어붙힌다.

다 붙히면 중복 없어지고 종료

import sys
input = sys.stdin.readline

def dfs(left, right, string):
    if len(string) == target:
        answers.add(string)
        return
    if left > 0:
        dfs(left - 1, right, string + N[left - 1:right + 1])
    if right < n:
        dfs(left, right + 1, string + N[left: right + 2])

N = input().rstrip()
n = len(N)
target = n * (n + 1) // 2
answers = set()
for i in range(n):
    dfs(i, i, N[i])
print(len(answers))

2번 풀이 : 하나씩 지우는 방법

앞이나 뒤 분기를 나눠하나씩 지우다가 남은 문자가 다 같은 문자면 압축시키고 종료

def dfs(string):
    global cnt
    if len(n) == 1:
        cnt +=1
        return
    L = set(list(string))
    if len(L) == 1:
        cnt+=1
        return
    else:
        dfs(string[1:])
        dfs(string[:-1])

n = input()
cnt = 0
dfs(n)
print(cnt)