오늘의 알고리즘(백준 7490)

1. 백준 7490, 0 만들기 

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

7490번: 0 만들기

 

---

2. 요구사항 

- 첫번째 입력값은 테스트 케이스의 개수(N < 10)가 주어진다. 

   ex) 2가 입력된다면, 테스트 케이스가 2개라는 뜻 

 

- 그 다음 N개 만큼 테스트 할 숫자의 범위(3 <= N <= 9)가 입력된다. 

   ex) N이 2인 상태에서 3, 7이 입력된다면 첫번째 케이스는 1~3, 두번째 케이스는 1~7의 오름차순 수열을 의미한다. 

 

- 수열 사이에 +, - , 공백을 사용하여 하나의 수식을 만든다.

 

- 만들어진 수식의 연산 결과가 0이 되는 모든 수식을 찾는다. 

 

---

3. 어떻게 풀까? 

- 어떻게 수열을 수식화하여 0으로 만드는지 그 규칙성을 생각해보았다.

- 30분동안 붙잡았는데 잘 모르겠다. 

- 그냥 바로 해답으로 가자. 

 

---

4. 해설 

- 수열의 범위가 최대 3~9 까지 이므로, 완전 탐색으로 문제를 해결할 수 있다. 

- 수열을 담은 배열과 연산자를 담은 배열로 나누어 해결해볼 수 있다. 

 

N이 3인경우, [1,2,3] 수열이 작성되고 연산자가 들어갈 수 있는 공간은 다음과 같다. 

- 1과 2사이 

- 2와 3사이

 

그럼 2개 연산자의 조합을 경우의 수(3의 n-1승)를 만들어 보면 다음과 같다. 

[공백 , 공백] [공백 , +] [공백 , -]

[+ , +] [+ , 공백] [+ , -]

[- , -] [- , 공백] [- , +]

 

총 9가지의 경우의 수가 나온다. 

이를 기반으로 생각해보면, 최대로 연산하는 경우의 수는 3의 8승(약 3만개) 이다.

 

 

---

5. 코드 

import copy

def recursive(array, n): 
    if len(array) == n:
        operators_list.append(copy.deepcopy(array))
        return
    array.append(' ')
    recursive(array, n)
    array.pop()

    array.append('+')
    recursive(array, n)
    array.pop()

    array.append('-')
    recursive(array, n)
    array.pop()
    
test_case = int(input())
for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([], n - 1)

    integers = [i for i in range(1, n + 1)]

    for operators in operators_list:
        string = ""
        for i in range(n - 1):
            string += str(integers[i]) + operators[i]
        string+= str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

---

6. 참고자료

 

https://wikidocs.net/16038

위키독스

 

 

https://blockdmask.tistory.com/437

[python] 파이썬 eval 함수 정리 및 예제

 

 

https://bluese05.tistory.com/64

python eval() 함수 - 사용을 조심해야 하는 이유