Jin의 일상

문제설명

1. N으로 3이 주어졌다면, 수열 1 2 3이 생성됐음을 의미한다. (3 <= N <= 9)

2. 각 숫자 사이에는 '+' 또는 '-', '  '가 들어간다.

(' '는 숫자를 이어 붙이는 것을 의미한다. 예를 들어 2 3이라면, 23이 된 것이다.)

3. n이 주어졌을 때 수열 사이에 '+', '-', ' ' 을 넣은 후 0이 나오는 수식을 ascii 순서에 따라 출력해야 한다.

알고리즘

1. DFS를 통해 수열 사이에 들어간 문자 형태의 경우의 수를 구한다.

  - ASCII 순서에 따라 수식을 출력하라고 했으므로, [' ', '+', '-']가 되어야 합니다. 

  - 답이 틀렸을 시에는 ASCII 순서로 작성되지 않았는지 확인합니다.

2. 경우의 수가 되는 형태 마다 0이 되는지 계산한다.

  - N개의 수열이 모두 들어간 상태에서 0이 되는지 확인해야 하므로, 가지치기(컷팅)가 되지 않습니다

'  ', '+', '-'의 ASCII 순서 비교

# ' '가 '+'보다 작다.
print(ascii(' ') < ascii('+'))  # TRUE

# ' '가 '-'보다 작다
print(ascii(' ') < ascii('-'))  # TRUE

# '+'가 '-'보다 작다
print(ascii('+') < ascii('-'))  # TRUE

# 따라서...  ' ' --> '+'  --> '-'

함수설명

- replace : 블로그 참고 [ gaza-anywhere-coding.tistory.com/21?category=827729 ]

- eval : string으로 주어진 수식에서 숫자와 부호를 구분하여 계산합니다. 결과 값은 int로 리턴됩니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def calculator(form):
    form = form.replace(" ", '')
    return eval(form)


def DFS(L, form):
    if L == n:
        tot = calculator(str(form))
        if tot == 0:
            print(form)
        return

    else:
        for x in [' ', '+', '-']:
            transform = str(form) + x + str(r[L+1])
            DFS(L+1, transform)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n = int(input())
        r = list(range(n+1))
        DFS(1, 1)
        print()