https://www.acmicpc.net/problem/14888
#14888: 연산자 삽입
숫자 N(2 ≤ N ≤ 11)의 수는 첫 번째 줄에 있습니다.
A1, A2, …, AN은 두 번째 줄에 지정됩니다.
(1 ≤ Ai ≤ 100) 세 번째 줄은 4개의 정수를 제공하며 그 합은 N-1이고 다시 덧셈 횟수(+), 뺄셈 횟수(-),
www.acmicpc.net
N개의 숫자 A1, A2, …, AN의 시퀀스가 주어집니다.
또한 N-1 연산자를 사용하여 숫자 사이에 삽입합니다.
연산자는 더하기(+), 빼기(-), 곱하기(×), 나누기(÷)로만 구성됩니다.
숫자와 숫자 사이에 연산자를 넣어 식을 만들 수 있습니다.
이 때 주어진 숫자의 순서를 변경하지 마십시오.
예를 들어 6개의 수열이 1, 2, 3, 4, 5, 6이고 주어진 연산자가 2개의 덧셈(+), 1개의 뺄셈(-), 1개의 곱셈(×), 1개의 나누기(÷ )라고 가정합니다.
), 총 60개의 표현식을 생성할 수 있습니다.
예를 들어 다음과 같은 식을 만들 수 있습니다.
- 1+2+3-4×5÷6
- 1÷2+3+4-5×6
- 1+2÷3×4-5+6
- 1÷2×3-4+5+6
식 평가는 다시 시작하고 연산자 우선 순위를 무시해야 합니다.
또한 나눗셈은 몫을 정수 나눗셈으로 취합니다.
음수를 양수로 나눌 때는 C++14 표준을 따릅니다.
즉, 양수로 바꾼 다음 몫을 취하고 그 몫을 음수로 바꾸는 것과 같습니다.
따라서 위 4개의 식의 결과는 다음과 같이 계산된다.
- 1+2+3-4×5÷6 = 1
- 1÷2+3+4-5×6 = 12
- 1+2÷3×4-5+6 = 5
- 1÷2×3-4+5+6 = 7
N개의 숫자와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 표현식의 최대 결과와 최소 결과를 찾는 프로그램을 작성하십시오.
기입
숫자 N(2 ≤ N ≤ 11)의 수는 첫 번째 줄에 있습니다.
A1, A2, …, AN은 두 번째 줄에 지정됩니다.
(1 ≤ AI ≤ 100) 세 번째 줄은 더하기(+), 빼기(-), 곱하기(×), 세분 수(÷)의 합이 N-1인 네 개의 정수를 제공합니다.
).
누르다
첫 번째 줄에서 만들 수 있는 식의 결과 중 최대값을 두 번째 줄에서 최소값을 반환합니다.
연산자를 삽입하는 방법에 관계없이 -10억보다 크거나 같고 10억보다 작거나 같은 결과를 반환하는 입력만 반환됩니다.
또한 중간에 계산한 식의 결과는 처음부터 항상 -10억보다 크거나 같고 10억보다 작거나 같습니다.
문제를 해결하다
처음에 숫자의 순서를 바꾸면 안된다는 글을 못읽고 제법 복잡한 코드를 썼는데 이게 실버라니…? 나는 그것을 다시 읽었다.
주어진 숫자의 순서를 변경하지 마십시오.. 어설프게 읽지말고 글을 똑바로 읽자
그래서 훨씬 쉽습니다.
숫자의 순서가 고정되어 있고 연산자만 변경하면 되므로 DFS가 문제를 해결합니다.
오퍼레이터별로 케이스를 나누어 실행한 후 재귀 호출을 통해 검색했습니다.
#연산자 끼워넣기
N = int(input())
A = list(map(int, input().split()))
cal = list(map(int, input().split())) # +, -, x, / 순서
maximum, minimum = -1e9, 1e9
#이 solution을 계속 돌리면서 계산 끝나면 max, min 리턴하고 끝
def solution(cnt, sum, plus, minus, multiple, divide):
global maximum, minimum
if cnt == N:
maximum = max(sum, maximum)
minimum = min(sum, minimum)
return
if plus:
solution(cnt+1, sum+A(cnt), plus-1, minus, multiple, divide)
if minus:
solution(cnt+1, sum-A(cnt), plus, minus-1, multiple, divide)
if multiple:
solution(cnt+1, sum*A(cnt), plus, minus, multiple-1, divide)
if divide:
solution(cnt+1, int(sum/A(cnt)), plus, minus, multiple, divide-1)
solution(1, A(0), cal(0), cal(1), cal(2), cal(3) )
print(maximum)
print(minimum)아무 생각 없이 분단의 시작에서
// A(cnt)를 합산했는데 테스트 케이스 3에서 즉시 오류가 발생했습니다.
제약 조건에 나눗셈 조건이 많아서 다시 확인해보니,
즉, 양수로 바꾼 다음 몫을 취하고 그 몫을 음수로 바꾸는 것과 같습니다.
이 경우로 구성
위의 차이가 발생하므로 int(sum/A(cnt))로 변경하면 오류가 사라집니다!