[Python] 백준 #14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

 

 

내 코드

import sys
from itertools import permutations

N = int(input())
num = list(map(int,sys.stdin.readline().split()))
tmp = list(map(int,sys.stdin.readline().split()))
arr = []
cnt=0
for i in tmp:
    cnt+=1
    for j in range(i):
        arr.append(cnt)

p = set(permutations(arr,len(arr)))
l = []
for tuple in p:
    sol=num[0]
    tmp=num[1:]
    for n,op in zip(tmp,tuple):
        if op == 1:
            sol+=n
        elif op == 2:
            sol-=n
        elif op==3:
            sol*=n
        else:
            if(sol<0):
                sol*=-1 
                sol//=n
                sol*=-1
            else:
                sol//=n
    l.append(sol)

print(max(l))
print(min(l))

+->1, -->2, *->3, %->4로 정의하여 연산자들을 arr 리스트에 넣어주었다.

그 다음에 순열을 사용하여 연산자들의 경우의 수를 다 구해주었다.

zip으로 숫자와 연산자들을 하나하나 빼주면서 답을 구했다.

이때 순열은 집합으로 구해야지 시간초과가 나지 않는다!

 

 

 

 

다른사람 코드

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

백드래킹(DFS)로 푼 방법이다. 어렵다..! 

dfs로 모든 경우의 수를 다 구해주었다. depth가 dfs로 들어간 횟수이다. 이 횟수가 수의 갯수와 같을때 max,min을 구해서 return 해준다. 

이제 dfs 재귀부분을 보자! +,-,*,%일때의 조건을 다 나눠주었다. 그 조건에 들어갈때마다 dfs를 해주는데 깊이는 1이 늘어나고 total에 알맞는 계산을 해주고 넘긴다. 그리고 연잔자의 수를 -1 해준다.

 

 

 

이렇게 경우의 수를 구할 때 나는 무조건 순열, 조합을 사용하는데 이렇게 백트래킹을 사용할 수 있다는 것을 처음알았다. 어렵지만 하나씩 해가면,, 언젠가는 코테 천재가 될 수 있겠지?! 그때까지 화이팅!!!!

 

 

 

다른사람 코드 출처 - https://velog.io/@kimdukbae/BOJ-14888-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0-Python