난이도

Gold 5

풀이 참고 유무

O

막힌 부분

1. eval함수를 생각하지 못함.
2. 1의 이유로 문자열을 한번에 계산하지 않고 재귀할 때마다 계산함.

문제

문제 바로가기

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

문제 검토

딱 봤을 떄부터 브루트 포스인 건 알겠지만, 구현이 조금 어려울 수도 있겠다.

풀이(python)

Python

Te=int(input())
ch=list()
# import sys
# sys.setrecursionlimit(100000)
def divide(now,res):
    if now>n:        
        tmp=res.replace(' ','')
        if eval(tmp)==0:
            print(res)
        return
    divide(now+1,res+' '+str(now))
    divide(now+1,res+'+'+str(now))
    divide(now+1,res+'-'+str(now))
    

for _ in range(Te):
    n=int(input())
    res='1'
    now=1
    divide(2,res)    
    print() 

먼저 재귀를 통해 문자열을 완성하고 eval 함수로 한번에 계산한다.

걸린 시간

X

총평

재귀를 사용하는 것까지는 접근했지만, 재귀할 때마다 계산한 것이 문제를 굉장히 복잡하게 만들었다.
eval, replace 등의 라이브러리 함수들을 잘 익히고 활용하자.