백준 문제풀이

[백준(BOJ)/C++] 14888번: 연산자 끼워넣기 - 코딩밥상

코딩밥상 2022. 8. 9. 16:57

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

 

 

  • 접근 방법, 논리 흐름(알고리즘)

 문제에서 요구하는 것은 문제에서 주어진 연산자를 사용하여 계산 결과의 최댓값과 최솟값이다.

단 숫자의 순서는 유지하고 연산자의 우선순위 또한 고려하지 않고 순서대로 계산하면 되는 문제이다.

시간 제한도 넉넉하고 연산자의 갯수가 최대 10개라서 완전탐색을 하면 되겠다.

연산자의 순서에 따라 결과값이 달라지기 때문에 전 문제와 동일한 방법으로 연산자를 저장하여 순열로 모든 경우의 수를 저장하고 계산 후 비교하면 되겠구나 생각했다.

문제의 주안점을 연산자로 두고 주어진 연산자의 개수만큼 해당 연산자의 번호로 vector에 저장했다. (1 -> '+' , 2 -> '-' , 3 -> '*' , 4 -> '/')
완전탐색으로 연산자의 가능한 순서를 모두 비교한 후에 최댓값과 최솟값을 최신화 해주었다.
앞에서부터 순서대로 계산해준다.

이 문제 또한 순열로 모든 경우의 수를 비교하고 답을 구하는데, 키 포인트는 연산자의 저장 방법과 계산을 어떻게 구현하는지였다