[BaekJoon] 7490 0 만들기 (Gold 5) - Python

문제

 

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

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

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

---

입출력 예시

 

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

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

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

 

입력예시1)

2
3
7

출력예시1)

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

---

코드

 

이 문제......

dfs랑 브루트포스 같이 쓰는거같다

dfs함수 작성하다보니,,,,,,,,,,,,,,,,,,,

모든 경우의 수 다 지나가던데 ㅇ.ㅇ

 

아래 코드에 더 자세하게 적어놨따.

 

def dfs(index, array, n): # dfs함수 정의 - 맨 마지막 인덱스까지 간 경우, eval함수를 이용하여 결과값을 계산하고 결과값이 0일 때 해당 식을 출력한다. 그 전까지는 계속해서 연산기호를 추가한다.
    if index == n - 1: # 인덱스 번호와 n - 1의 값이 같은 경우 = 끝까지 이동한 경우
        if eval(''.join(map(str, array))) == 0: # 식을 문자열로 변환 후 계산한 결과값이 0인 경우
            for i in range(len(array)): # array의 길이만큼 반복하여 i증가
                if array[i] == '': print(' ', end = '') # 만약 i번째 문자가 ''라면, 공백(' ') 출력, 마무리 문자는 ''로 설정
                elif i == len(array) - 1: print(array[i]) # 만약 인덱스 번호가 맨 마지막이라면 array[i] 출력 후 줄바꿈
                else: print(array[i], end = '') # 아무 해당사항 없으면 array[i]출력 후 줄바꿈 안함
    else: # 아니라면
        x = index * 2 + 1 # 홀수번째 인덱스 번호 계산
        array.insert(x, '') # x번째 인덱스에 '' 삽입
        dfs(index + 1, array, n) # dfs함수 재귀호출
        array.pop(x) # x번째 인덱스 제거

        array.insert(x, '+') # x번째 인덱스에 '+' 삽입
        dfs(index + 1, array, n) # dfs함수 재귀호출
        array.pop(x) # x번째 인덱스 제거

        array.insert(x, '-') # x번재 인덱스에 '-' 삽입
        dfs(index + 1, array, n) # dfs함수 재귀호출
        array.pop(x) # x번째 인덱스 제거

T = int(input()) # 테스트케이스를 입력한다
for _ in range(T): # 테스트케이스 만큼 반복한다
    N = int(input()) # N을 입력받는다
    num = [i for i in range(1, N + 1)] # 1 ~ N까지의 원소를 갖는 리스트를 생성한다
    dfs(0, num, N) # 위의 리스트와 N을 dfs함수의 매개변수로 전달하여 dfs함수를 호출한다
    print() # 줄바꿈

---

실행 화면

 

---

채점 결과

처음에 작성한 코드는 itertools에 있는 product함수 이용해서 중복순열 구해서 풀었는데,,, 틀렸다더라 ㅇ.ㅇ

아숩아숩