[백준] 7490. 0 만들기

문제

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

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

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

입력

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

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

출력

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

 

---

수열의 모든 숫자 사이에 " ", "+", "-" 세 가지 연산 중 하나를 넣어 계산하고, 0이되는 수식을 출력하는 문제다.

예제 입출력은 다음과 같다.

 

CASE	INPUT	OUTPUT
1	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

 

연산이 세 종류이므로 각 테스트 케이스마다 3^(N-1)가지의 경우가 나올 수 있고, 각 테스트 케이스의 수는 최대 9이므로 최대 3^8 == 6,561가지의 경우가 있다.

따라서 테스트 케이스의 수가 10 미만이므로, 최대 65,610가지의 경우의 수로 해결이 가능하므로 백트래킹을 통해 문제를 해결할 수 있다.

아이디어는 다음과 같다.

 

첫 번째 시도

이분법을 재귀 함수로 구현하여 해결하고자 했다.

1. 재귀 함수로 수열을 String 형태로 입력받는다.

 1-1) 수열을 반으로 나눌 수 없으면 그대로 return 한다.

 1-2) 수열을 반으로 나눌 수 있으면 2.를 진행한다.

2. 수열을 반으로 나누어 왼쪽과 오른쪽 수열로 구분한다.

 왼쪽 수열을 이분한 것과 오른쪽 수열을 이분한 것 사이에 세 가지 연산을 넣어 return한다.

 

작성 코드

def zerosum(seq):
    n = len(seq) // 2
    if n == 0:
        return seq
    else:
        l_seq = seq[:n]
        r_seq = seq[n:]
        oper = ["", "+", "-"]

        for i in range(3):
            form = zerosum(l_seq) + oper[i] + zerosum(r_seq)
            print(form)
            if eval(form) == 0:
                print("zero", form)
            return form

s = "1234567"
zerosum(s)

# result
# 23
# 123
# 45
# 67
# 4567
# 1234567

결과는 실패...

아무것도 출력이 되지 않아 form을 매번 출력하도록 했더니 결과가 저렇게 나왔다.

곰곰히 생각해봤더니 for문에서 i == 0일때마다 return을 해서 다른 연산자를 수열 사이에 추가할 수 없었다.

return을 쓰지 않는 방향으로 생각해보았는데 도저히 생각이 안나서 실패

 

두 번째 시도

수열 사이에 들어갈 연산자 조합을 만든다.

1. 재귀 함수로 수열의 크기와 연산자 조합을 받는다.

 1-1) 연산자 조합의 갯수가 (수열의 크기-1)이면 조합을 연산자 리스트에 추가한다.

 1-2) 연산자 조합의 갯수가 (수열의 크기-1)보다 작으면 2.를 진행한다.

2. 반복문으로 연산자 조합에 연산자를 추가한다.

 2-1) 연산자 조합에 " ", "+", "-" 중 하나를 순서대로 추가한다.

 2-2) 새로운 연산자 조합으로 1.을 진행한다.

 2-3) 연산자 조합에서 추가한 연산자를 제거한다.

 

이렇게 연산자 리스트에 모든 연산자 조합을 저장할 수 있다.

이제 수열 사이에 연산자 조합을 넣어 계산하면 된다.

 

작성 코드

# 7490. 0 만들기
# recursion

# n : 수열 길이, oper : 하나의 식에서 연산자 조합
def operation(n, oper):
    op = [" ", "+", "-"]
    if len(oper) == n-1:
        oper_list.append(oper[:])
        return
    else:
        for i in range(3):
            oper.append(op[i])
            operation(n, oper)
            oper.pop()

n = int(input())

for _ in range(n):
    oper_list = []	# 모든 경우의 연산자 조합
    seq = [str(x+1) for x in range(int(input()))]
    operation(len(seq), [])

    for op in oper_list:
        formula = "1"
        for j in range(len(seq)-1):
            formula += op[j] + seq[j+1]
        if eval(formula.replace(" ", "")) == 0:
            print(formula)
    print()	# 테스트 케이스마다 한 줄 띄워 구분

 

넘모 어려웠다..

 

참고

• oper_list.append(oper[:])

파이썬의 모든 것은 객체입니다. oper를 그대로 append하게 되면 함수를 벗어났을 때 oper 객체가 사라지므로 oper_list에 아무것도 남지 않아요. [:]를 지우고 실행해보시면 알 수 있습니다.

• eval()

eval() 안의 수식을 계산하여 값을 리턴합니다. 형식은 String 형식으로 입력해야 해요~

• replace()

문자열 내의 값을 치환합니다. name = "baekjoon"이고, name.replace("a", "b")를 하게 되면 문자열의 모든 "a"를 "b"로 치환하여 "bbekjoon"을 리턴합니다.