728x90
https://acmicpc.net/problem/14888
n = int(input())
n_list = list(map(int, input().split()))
operator = list(map(int, input().split()))
min_val = 1000000000
max_val = -1000000000
def backtrack(index, number=n_list[0]):
if index == n - 1:
global min_val, max_val
if min_val > number:
min_val = number
if max_val < number:
max_val = number
return
else:
if operator[0]:
operator[0] -= 1
backtrack(index + 1, number + n_list[index + 1])
operator[0] += 1
if operator[1]:
operator[1] -= 1
backtrack(index + 1, number - n_list[index + 1])
operator[1] += 1
if operator[2]:
operator[2] -= 1
backtrack(index + 1, number * n_list[index + 1])
operator[2] += 1
if operator[3] and n_list[index + 1]:
operator[3] -= 1
backtrack(index + 1, int(number / n_list[index + 1]))
operator[3] += 1
backtrack(0)
print(max_val,min_val, sep='\n')
이전에 풀었던 문제들처럼 pypy에서만되고 python에서 안될줄 알았는데 오히려 python에서 더 빨랐다.
백트래킹을 사용해서 모든 조합을 확인하는 방법으로 진행했다
나누기 부분에서 조금 시간이 걸렸다.
예제 3번에서 max값이 계속 48이 나왔는데 나누기 연산자를 '//' 로 하면 음수일때 원하는 값이 나오지 않는다.
그래서 나누고 '/'를 사용했더니 성공하였다.
'STUDY > Algorithm' 카테고리의 다른 글
[SWEA] 1949 등산로 조성, 모의 SW 역량테스트, python (0) | 2021.03.11 |
---|---|
[백준, SWEA] BOJ 14889 스타트와 링크, swea4012 요리사 (0) | 2021.03.10 |
[백준] 9663 N-Queen (0) | 2021.03.10 |
[백준] 2580 스도쿠 (0) | 2021.03.09 |
[백준] 2589 보물섬 (0) | 2021.03.08 |