문제 링크 : https://www.acmicpc.net/problem/14888
문제
모든 경우의 수를 구하지않고 하는 방법이 있을까?
이 문제에서는 ‘숫자는 고정' 된 상태에서 ‘연산자 순서를 변경' 해서 최대,최소값을 확인하는것이다 과연 이 문제에서 모든 경우의 수를 구하지않고 하는 방법이 있을까?
쉽지않을것같아서 완탐, BFS, DFS계열로 눈을 돌렸다
굳이 BFS, DFS로 돌려야하나 ?
가만 생각해보니 무조건 모든 연산자를 다 돌려야하는데, 굳이 BFS,DFS로 돌려야 싶었다.
BFS나 DFS는 ‘특정 조건이 충족되면 진행' 하는거에 특화되어있는거지, 모든 연산을 확인해야하는 경우에 굳이 써야하는 이유를 모르겠어서 안썻다
완탐
완전탐색. 모든 경우의 수에 하나씩 대입해보면서 결과를 확인한다
연산자 순서 결정하기
#arrs 는 + - * / 횟수가 적혀있는 배열
something = ['+','-','*','/']
strs = ""
for i,j in zip(arrs, something) :
strs += (j*i)
from itertools import permutations
temps = list(permutations(strs))
모든 연산자의 총 횟수를 하나의 strs로 모은 뒤에 permutations를 사용해서 순열을 만든다
중복되는 순열이 있을수도 있다. 그러나 시간초과나 메모리초과가 나지않아서 신경쓰지않았다
소스코드 (전체)
# N = 6
# datas = [1, 2, 3, 4, 5, 6]
# arrs = [2, 1, 1, 1]
import sys
input = sys.stdin.readline
N = int(input().strip())
datas = list(map(int , input().split()))
arrs = list(map(int , input().split()))
something = ['+','-','*','/']
strs = ""
for i,j in zip(arrs, something) :
strs += (j*i)
from itertools import permutations
temps = list(permutations(strs))
max_result = -999999999
min_result = 999999999
for temp in temps :
result = datas[0]
for data in zip ( datas[1:],temp) :
if data[1] == '+' :
result += data[0]
elif data[1] == '-' :
result -= data[0]
elif data[1] == '*' :
result *= data[0]
else :
if result >= 0 :
result //= data[0]
else :
result = (result*(-1) // data[0]) *(-1)
max_result = max(max_result,result)
min_result = min(min_result,result)
print(max_result)
print(min_result)
'CodingTest' 카테고리의 다른 글
리트코드 Tapping Rain Water (0) | 2022.07.13 |
---|---|
백준 2606 바이러스 (0) | 2022.07.13 |
백준 11725 트리의 부모 찾기 파이썬 (0) | 2022.07.05 |
백준 1260 DFS와 BFS (0) | 2022.07.05 |
프로그래머스 72411 메뉴리뉴얼 파이썬 (0) | 2022.07.01 |