[백준-파이썬] 7490: 0 만들기

문제 보러 가기!

가지치기 없이 그냥 DFS로 풀었다~
N의 범위가 작아서, 그냥 해도 되는 것 같다!
시간 복잡도는 3^9 * 10 인데, 계산하면 196,830. 1초 내에 충분히 계산될 수 있다.

DFS로 하고 DFS에 history와 idx를 만들었다.
idx는 1부터 N까지 어떤 숫자를 볼 차례인지 담당한다. idx가 N+1이 되면 숫자를 다 본 것이다. 이때 수식의 결과가 0이 되는지 체크하면 된다!
idx가 N+1 미만일 때는, 매번 +, -, 공백(숫자 이어지는 것) 의 경우로 재귀를 돈다.

헷갈렸던 부분!

• 바로 바로 idx가 N+1될 때 출력하면 안되어서(ASCII 순서에 따라서 출력하라고 함), 되는 경우를 리스트에 넣었다가 정렬한 후에 출력했다.
• ㅠㅠㅠ 계속 '출력 형식이 잘못되었습니다!'가 나왔다. 아니 맞왜틀..!!!! 이었는데, ' 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.' 이런 문구가 있는 걸 보고 수정하니.. 맞았다... 역시 문제를 잘 읽는 게 젤 중요한 것 같다..

코드

import copy
import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().strip().split())


def dfs(idx, curr_num, history):
    global ans
    if idx == N + 1:  # 끝까지 옴
        tmp = ''.join(map(str, history)).replace(' ', '')  # 결과식(숫자 붙임)
        if eval(tmp) == 0:  # 결과가 0이 된다면
            ans.append(''.join(map(str, history)))
        return

    history_copy1 = copy.copy(history)
    history_copy1.extend(['+', idx])
    dfs(idx + 1, curr_num + idx, history_copy1)

    history_copy2 = copy.copy(history)
    history_copy2.extend(['-', idx])
    dfs(idx + 1, curr_num - idx, history_copy2)

    history_copy3 = copy.copy(history)
    t = history_copy3[-1]
    tmp = t * 10 + idx - t
    history_copy3.extend([' ', idx])
    dfs(idx + 1, tmp, history_copy3)


T = int(input().strip())
for _ in range(T):
    N = int(input().strip())
    ans = []
    dfs(2, 1, [1])
    ans.sort()
    for a in ans:
        print(a)
    print()

import sys

input = sys.stdin.readline
MIIS = lambda: map(int, input().strip().split())


def dfs(idx, history):
    global ans
    if idx == N + 1:  # 끝까지 옴
        tmp = history.replace(' ', '')  # 결과식(숫자 붙임)
        if eval(tmp) == 0:  # 결과가 0이 된다면
            ans.append(history)
        return

    dfs(idx + 1,  history+f'+{idx}')

    dfs(idx + 1,  history+f'-{idx}')

    dfs(idx + 1, history+f' {idx}')


T = int(input().strip())
for _ in range(T):
    N = int(input().strip())
    ans = []
    dfs(2, '1')
    ans.sort()
    for a in ans:
        print(a)
    print()

처음에는 위에 꺼처럼, 그때까지 계산한 숫자(curr_num)도 데리고 다니다가.. 근데 그 숫자가 좀 이상해지고 ㅠㅠ(숫자 붙일 때 처리를 잘못했다.)  필요도 없어서 안 썼다.