[BOJ] 14888번 연산자 끼워넣기 (C++)

문제 링크 (https://www.acmicpc.net/problem/14888)

 

next_permutation을 사용하여 해결한 문제!

N개의 수로 이루어진 수열을 num 벡터에 차례대로 넣어준다.

연산자의 개수만큼 연산자에 해당하는 숫자를 oper 벡터에 넣어주었다. 이 때, 연산자에 해당하는 숫자는 (1: 덧셈 / 2: 뺄셈 / 3: 곱셈 / 4: 나눗셈)이라고 지정했다.

예를 들어 연산자 입력이 2 1 1 1 이라면 => oper 벡터에는 1 1 2 3 4 가 들어가는 것!

 

oper 벡터를 next_permutation 의 인자로 사용하여 순열을 구해준다. do문 안에서는 num 벡터의 크기만큼 반복문을 돌리며 각 연산자에 맞는 연산을 해준다. (1: 덧셈 / 2: 뺄셈 / 3: 곱셈 / 4: 나눗셈)

각 순열마다 최대/최소값을 비교하고 마지막에 값을 출력해준다.

---

[소스코드]

---

2021-08-06

Silver 1

알고리즘 분류

 - 브루트포스 알고리즘

 - 백트래킹