문제 링크

문제 소개

해당 문제는 1부터 N까지의 수열의 중간중간에 연산(+,-,공백)을 넣게되었을 때 결과가 0이 되는 수식의 결과를 찾는 문제이다.

문제 분석

처음 봤을 때, 다양한 방법으로 풀수있음을 느꼈다. 수열이 정해져 있고 중간에 어떠한 연산자가 들어가냐에 따라 달라지기 때문에 DFS와 같은 브루트포스 알고리즘을 사용해도 될것같고, DP를 사용해도 가능할 것 같았다.

해결책1(글쓴이 해결책)

1부터 N까지의 범위를 작게 나눠서 f(n+1) = f(n) + (특정 연산자) 과 같이 생각해볼수 있다. 그리고 해당 문제에는 3가지 연산자가 있기 때문에 3xN 리스트를 생성하였고 0번째 행은 +, 1번째 행은 -, 2번째 행은 공백을 진행했을 때 결과값을 저장해줄 것이다. 그럼으로 맨 처음 수(1)는 아래와 같이 들어갈것이다.

N = int(input().rstrip('\n'))
    board = [[set() for _ in range(N + 1)] for _ in range(3)]
    board[0][0], board[1][0], board[2][0] = set([(0, '', '')]), set([(0, '', '')]), set([(0, '', '')])
    board[0][1], board[1][1], board[2][1] = set([(1, '1', '1')]), set([(1, '1', '1')]), set([(1, '1', '1')])

위의 board의 원소는 set([전체 합(숫자), 마지막 숫자(문자열), 전체 수식(문자열)])이다. 위와 같이 둔 이유는 공백 연산자를 계산하기 위해 분리해둔 것이다.

    for n in range(2, N+1):
        for i in range(3):
            for tempNum, tempStr, tempAll in board[i][n-1]:
                board[0][n].add((tempNum + n, str(n), tempAll + '+' + str(n)))
                board[1][n].add((tempNum - n, str(-n), tempAll + '-' + str(n)))
                board[2][n].add((tempNum - int(tempStr) + int(tempStr + str(n)), tempStr + str(n), tempAll + ' ' + str(n)))

위의 코드와 같이 어떠한 특정 수(n)를 추가할때 전의 조합들(board[i][n-1])에서 각각 꺼내서 그 조합에 +,-공백을 추가했을 때의 결과를 다음 step에 넣는 느낌으로 코딩하였다.

여기서 헷갈릴만한 점은 공백을 처리하는 점인데, 어떠한 수식에서 공백을 추가할 때 2가지로 나눠 생각할 수 있다.

1. +나 -가 없을 경우
2. 앞서 +나 -을 했을 경우

위의 두가지 모두 전의 조합들(board[i][n-1])에서 꺼낸 전체 합(숫자) tempNum, 마지막 숫자(문자열) tempStr, 전체 수식(문자열) tempAll에서 먼저 다음 전체 합은 이전에 계산했던 마지막 값을 없애고(-int(tempStr)) 공백을 통해 합친 값(+int(tempStr + str(n)))을 새로 더하였다.

그리고 마지막으로 마지막 열의 원소값을 따로 리스트에 모아 sort하고, 전체 합이 0인 것들만 출력하였다.

이렇게 dp의 메모이제이션 기법을 사용해서 해결하였다.

전체 코드

import sys


def makeZero():
    N = int(input().rstrip('\n'))
    board = [[set() for _ in range(N + 1)] for _ in range(3)]
    board[0][0], board[1][0], board[2][0] = set([(0, '', '')]), set([(0, '', '')]), set([(0, '', '')])
    board[0][1], board[1][1], board[2][1] = set([(1, '1', '1')]), set([(1, '1', '1')]), set([(1, '1', '1')])

    for n in range(2, N + 1):
        for i in range(3):
            for tempNum, tempStr, tempAll in board[i][n - 1]:
                board[0][n].add((tempNum + n, str(n), tempAll + '+' + str(n)))
                board[1][n].add((tempNum - n, str(-n), tempAll + '-' + str(n)))
                board[2][n].add(
                    (tempNum - int(tempStr) + int(tempStr + str(n)), tempStr + str(n), tempAll + ' ' + str(n)))

    temp = [*board[0][-1], *board[1][-1], *board[2][-1]]
    temp.sort(key=lambda x: x[2])
    for a, b, c in temp:
        if a == 0:
            print(c)


def solution():
    T = int(input().rstrip('\n'))
    for t in range(T):
        makeZero()
        if t != T - 1:
            print()


input = sys.stdin.readline
solution()

해결책2(DFS)

해당 방법은 DFS와 eval함수를 사용하여 해결하였다.

eval함수는 시간복잡도 Average: O(n)로 시간초과가 발생할 수 있기 때문에, 코테에서는 사용하지 않는 것이 좋다.

# [gold-5] 7490 0 만들기
# algorithm 부루트포스, DFS
# 메모리:    29200 KB
# 시간:      160 ms
import sys
input = sys.stdin.readline

T = int(input())
result = []
operator = [' ', '+', '-']

def recursion(now,ans):
    if now == n+1:
        calc(ans)
        return
    for o in operator:
      recursion(now+1,ans+o+str(now))

def calc(ans):
    tmp = ans.replace(' ','')
    if eval(tmp) == 0:
        result.append(ans)

for _ in range(T):
  n = int(input())
  recursion(2,'1') # N은 3부터
  result.append(' ')

print(*result, sep='\n')

위의 코드도 각각의 연산자를 재귀문을 통해 돌리되, 수식을 차곡차곡 쌓아뒀다가 마지막에 eval함수를 통해 계산하여 0인 것들을 뽑아내는 방법이다.