0705_백준 알고리즘 #7490. 0 만들기

문제

https://www.acmicpc.net/problem/7490

 

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

---

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

---

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

---

코드

T = int(input())

def make_zero(i, cal):

    if i == N:
        if val(cal) == 0:
            ans.append(cal)
        return

    make_zero(i + 1, cal + '+' + str(seq[i]))
    make_zero(i + 1, cal + '-' + str(seq[i]))
    make_zero(i + 1, cal + ' ' + str(seq[i]))

def val(cal):

    s = 0
    num = ''
    before = 1  # 1: +, 2: -
    cal = cal.replace(' ', '') # 공백 제거

    for i in cal:
        if i.isdigit(): # 숫자인지 확인
            num += i
        else:
            if before == 1:
                s += int(num)
            elif before == 2:
                s -= int(num)
            num = ''
            if i == '+':
                before = 1
            elif i == '-':
                before = 2

    if num: # 마지막 데이터 처리
        if before == 1:
            s += int(num)
        elif before == 2:
            s -= int(num)

    return s

for _ in range(T):
    N = int(input())
    seq = list(range(1, N + 1))
    cal = str(seq[0])
    ans = []

    make_zero(1, cal)
    ans.sort()
    for res in ans:
        print(res)
    print()

 

※ 굉장히 길었던 코드 ..! 오늘도 알고리즘 분류와 티어를 보지 않고 풀다가 제출할 때 골드인거보고  바로 틀릴줄 알았는데 .. 

정답이라 나도 좀 얼떨떨했다 ㄷㄷ 백트래킹 코드까지는 빠르게 짰는데 문자열을 숫자로 바꿔서 계산할 때를 짜는게 오래 걸렸다. 역시 골드 문제에는 고려할 사항이 확 많아지는 것 같다. 오늘 문제에서도 데이터 형변환, 함수, 백트래킹, 브루트포스, 구현, 정렬 .. 참 다양하게 많이 들어갔당 ! 휴 ~ 그래도 오늘치 성공 ㅎㅎ