[백준] #7490 0만들기(python)

📌문제

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

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

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

입력

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

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

출력

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

예제 입력

2
3
7

예제 출력

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

백준 7490번 문제

💡Idea

➕, ➖, 공백을 이용하여 식을 만들어 그 결과가 0이 되는 식을 찾으면 되는 문제입니다.

따라서 저는 세 가지 경우를 끝까지 탐색할 수 있는 DFS를 이용하여 문제를 해결해보았습니다.

하지만 유의해야 할 점이 있습니다.

단순히 ➕, ➖만 있다면 해당 결과와 현재 수만을 인수로 넘겨주며 DFS를 진행해도 되지만, 공백이 있기 때문에 더해지거나 빼지는 수가 달라질 수 있으므로 이를 생각하면서 코드를 작성해야 합니다.

💻코드1

• ⏰ 시간 : 44 ms / 메모리 : 31256 KB

import sys
input = sys.stdin.readline

def evaluate(n, cur, sign, value, expression):
    if n >= N:
        value += (sign * cur)
        if value == 0: ans_set.add(expression)
    else:
        evaluate(n + 1, n + 1, 1, value + sign * cur, expression+'+'+str(n + 1))
        evaluate(n + 1, n + 1, -1, value + sign * cur, expression+'-'+str(n + 1))
        evaluate(n + 1, cur * 10 + (n + 1), sign, value, expression+' '+str(n + 1))

test_case = int(input())
for _ in range(test_case):
    N = int(input())
    ans_set = set()
    evaluate(1, 1, 1, 0, '1')
    print('\n'.join(sorted(ans_set)), end='\n\n')

📝코드1 설명

함수

• evaluate : ➕, ➖, 공백 이 세 가지 경우를 탐색하며 숫자 N까지 갔을 때 식의 결과가 0이 되면 해당 식을 ans_set에 추가해주는 함수

매개 변수

• n : 1부터 N까지의 수 중 현재 처리하고 있는 수
• cur : 현재 식에서 더하거나 빼야할 수
  EX) 1과 2 사이에 공백이 들어가 1 2가 된 경우에는 12가 값이 된다.
• sign : 현재 수를 더할 것인지 뺄 것인지를 나타내는 값으로, 1이면 더하기, -1이면 빼기이다.
• value : 이제 계산해주어야 하는 cur 값 이전까지 계산한 값
• expression : n번째 숫자까지 진행된 식 문자열

---

💻코드2

파이썬에는 매개변수로 받은 문자열 식을 계산해주는 eval이라는 함수가 존재합니다.

이 eval함수를 사용하면 가능한 식들만 만들어준 뒤 전부 계산해보면 되기 때문에 좀 더 간단하게 코드를 작성할 수 있습니다.

• ⏰ 시간 : 132 ms / 메모리 : 31256 KB

import sys
input = sys.stdin.readline

def solution(n, expression):
    if n >= N:
	    # 공백을 없애 계산 가능한 식으로 만들어 계산 후 0인지 확인
        if eval(expression.replace(' ', '')) == 0: 
            print(expression)
    else:
        n += 1
        solution(n, expression + ' ' + str(n))
        solution(n, expression + '+' + str(n))
        solution(n, expression + '-' + str(n))
        
test_case = int(input())
for _ in range(test_case):
    N = int(input())
    solution(1, '1')
    print()