문제
[실버1] https://www.acmicpc.net/problem/14888
해설 없이 스스로 풀었나요?
X
순열은 생각해냈으나 구현하지 못했음 / 백트래킹(DFS)는 구글링하여 이해함
재풀이 필요
아이디어
이 문제는 두가지로 풀 수 있다.
먼저 순열을 이용한 풀이이다.
처음에 내가 생각한 방법도 이것이다.
연산자 개수 (ex. [2, 1, 1, 1]) 를 입력받고, 이를 연산자 리스트로 변환한 후 (ex. ['+', '+', '-', '*', '/']) 이 리스트에 대해 n-1개를 고르는 순열을 구하면 된다.
이부분에 대한 나의 의문점은 ..comment로
구한 모든 경우에 수에 대해 완전탐색을 하며 식을 계산하면 만들 수 있는 식의 최대값과 최소값을 구할 수 있다.
두번째는 백트래킹, DFS를 이용한 풀이이다.
DFS 풀이는 연산자의 개수만큼 탐색하고, 연산자가 존재하면 해당 연산을 수행하고 재귀호출을 통해 더 깊이 탐색을 진행한다.
풀이
1. 순열
PyPy3 통과, Python3 시간초과
import sys
from itertools import permutations
n = int(input())
num = list(map(int, sys.stdin.readline().split()))
op_num = list(map(int, sys.stdin.readline().split()))
op_list = ['+', '-', '*', '/']
op = []
for i in range(4):
for j in range(op_num[i]):
op.append(op_list[i])
# print(op)
permu = list(permutations(op, n-1))
answer_max = -1e9
answer_min = 1e9
for case in permu:
total = num[0]
for i in range(1, n):
if case[i-1] == '+':
total += num[i]
elif case[i-1] == '-':
total -= num[i]
elif case[i-1] == '*':
total *= num[i]
elif case[i-1] == '/':
total = int(total / num[i])
# print(total)
if total > answer_max:
answer_max = total
if total < answer_min:
answer_min = total
print(answer_max)
print(answer_min)2. 백트래킹(DFS)
PyPy3 통과, Python3 통과
import sys
n = int(input())
num = list(map(int, sys.stdin.readline().split()))
op = list(map(int, sys.stdin.readline().split()))
answer_max = -1e9
answer_min = 1e9
def dfs(depth, total, add, sub, mul, div):
global answer_max, answer_min
if depth == n:
# print("depth == n {}".format(total))
answer_max = max(total, answer_max)
answer_min = min(total, answer_min)
return
if add:
# print("add", end = " ")
# print(depth, total, add, sub, mul, div)
dfs(depth+1, total+num[depth], add-1, sub, mul, div)
if sub:
# print("sub", end = " ")
# print(depth, total, add, sub, mul, div)
dfs(depth+1, total-num[depth], add, sub-1, mul, div)
if mul:
# print("mul", end = " ")
# print(depth, total, add, sub, mul, div)
dfs(depth+1, total*num[depth], add, sub, mul-1, div)
if div:
# print("div", end = " ")
# print(depth, total, add, sub, mul, div)
dfs(depth+1, int(total/num[depth]), add, sub, mul, div-1)
dfs(1, num[0], op[0], op[1], op[2], op[3])
print(answer_max)
print(answer_min)이게 무슨 소리인지.. 굉장히 오래 고민했다.
그리고 현재 주석처리 한 부분에 대해 주석을 해제하고 코드를 실행하면 이해가 완전히 된다.
아래 그림은 어떤 식으로 코드가 흘러가는지 직접 그려본 내용이다.
이런 식으로 재귀호출을 하며 가능한 모든 식을 만들며 total 값을 계산하다가, 깊이가 n이 되면 즉 모든 연산자를 이용했다면 최댓값과 최솟값과 비교하여 값을 갱신한다.
연산자 사용 순서에 따라 연산 결과가 달라진다.
모든 연산 순서를 고려하기 위해 연산자마다 모두 if문을 사용하였다.
이부분을 if-else로 하게 되면 모든 연산자 사용 순서를 고려할 수 없다.
Comment
1. 순열에 대한 의문
만약 입출력 예시3과 같이 같은 연산자가 여러개 있다면 순열을 구했을 때 같은 경우의 수가 무조건 등장할 것이다. 이러한 중복되는 것을 제외하고 경우의 수를 만들어야 할 것 같아 고민했는데 .. 모든 답안 예시가 그냥 중복을 포함해 순열을 구했더라구요. ? 더 고민이 필요한 부분이다.
무튼 이 코드는 python3에서 시간초과가 뜨므로 좋지 못한 코드임은 확실하다.
2. DFS 풀이가 무슨 말인가
단순하게 코드만 딱 보면 너무 이해가 되지 않는 코드이다.
DFS 개념을 다시 생각하며 하나의 출발점에서 깊게, 연산자를 모두 사용할 때까지 탐색한 후, 다시 돌아온다고 생각하니 조금씩 이해가 됐다.
위에 첨부한 그림을 보면 정말 이해가 더욱 잘 될 것이다!
3. 음수로 양수를 나눌 때
print(-3/2) # -1.5
print(int(-3/2)) # -1
print(-3//2) # -2
print(int(-3//2)) # -2
print(-3%2) # 1
print(int(-3%2)) # 1파이썬에서 / 연산을 하면, 음수 값을 양수로 변환해 몫을 취하고 그 몫을 음수로 바꾼다.
따라서 이 문제의 조건에 따르려면 //이 아닌, / 연산을 하고 int로 형변환을 진행하면 된다.
4. 최댓값과 최솟값 초기 설정
문제에서 식의 결과가 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과라고 하였으므로
최솟값은 10억으로, 최댓값은 -10억으로 설정한 후 값을 갱신해나간다.
1e9 = 1*10^9 = 10,0000,0000 으로 10억을 뜻한다.
