Jin의 일상

programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

1. 배열 변수인 numbers가 주어진다. ex) [1, 3, 4, 5, 2]

2. int형 변수인 target이 주어진다.

3. 각 numbers를 무작위로 더하거나 빼서 target 값과 같은 개수는?

문제 풀이

1. 모든 경우의 수를 찾아야 하므로 완전 탐색 문제 입니다.

2. 더하거나 뺐을 때 나오는 값을 재귀적으로 실행시킵니다.

3. 경우의 수가 만들어질 때 마다 target 값과 sum 값이 같은지 비교후 리턴 합니다.

  - 같다면, cnt를 1씩 올려줍니다.

4. cnt를 정답으로 제출합니다.

코드

def solution(numbers, target):
    def DFS(L, sum):
        nonlocal cnt
        if L == len(numbers):
            if sum == target:
                cnt += 1
            return
        else:
            plus = sum + numbers[L]
            DFS(L + 1, plus)
            minus = sum - numbers[L]
            DFS(L + 1, minus)
            
    cnt = 0
    DFS(0, 0) 
    return cnt

문제설명

1. N으로 3이 주어졌다면, 수열 1 2 3이 생성됐음을 의미한다. (3 <= N <= 9)

2. 각 숫자 사이에는 '+' 또는 '-', '  '가 들어간다.

(' '는 숫자를 이어 붙이는 것을 의미한다. 예를 들어 2 3이라면, 23이 된 것이다.)

3. n이 주어졌을 때 수열 사이에 '+', '-', ' ' 을 넣은 후 0이 나오는 수식을 ascii 순서에 따라 출력해야 한다.

알고리즘

1. DFS를 통해 수열 사이에 들어간 문자 형태의 경우의 수를 구한다.

  - ASCII 순서에 따라 수식을 출력하라고 했으므로, [' ', '+', '-']가 되어야 합니다. 

  - 답이 틀렸을 시에는 ASCII 순서로 작성되지 않았는지 확인합니다.

2. 경우의 수가 되는 형태 마다 0이 되는지 계산한다.

  - N개의 수열이 모두 들어간 상태에서 0이 되는지 확인해야 하므로, 가지치기(컷팅)가 되지 않습니다

'  ', '+', '-'의 ASCII 순서 비교

# ' '가 '+'보다 작다.
print(ascii(' ') < ascii('+'))  # TRUE

# ' '가 '-'보다 작다
print(ascii(' ') < ascii('-'))  # TRUE

# '+'가 '-'보다 작다
print(ascii('+') < ascii('-'))  # TRUE

# 따라서...  ' ' --> '+'  --> '-'

함수설명

- replace : 블로그 참고 [ gaza-anywhere-coding.tistory.com/21?category=827729 ]

- eval : string으로 주어진 수식에서 숫자와 부호를 구분하여 계산합니다. 결과 값은 int로 리턴됩니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def calculator(form):
    form = form.replace(" ", '')
    return eval(form)


def DFS(L, form):
    if L == n:
        tot = calculator(str(form))
        if tot == 0:
            print(form)
        return

    else:
        for x in [' ', '+', '-']:
            transform = str(form) + x + str(r[L+1])
            DFS(L+1, transform)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n = int(input())
        r = list(range(n+1))
        DFS(1, 1)
        print()