[백준] 14888.연산자 끼워넣기 (Swift)

코딩테스트/백준

도지대디 2022. 7. 7. 00:26

14888번: 연산자 끼워넣기

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

www.acmicpc.net

풀이

백트래킹으로 해결할 수 있는 문제입니다.

각 연산자의 개수가 들어있는 배열을 입력받고 나서 백트래킹을 이용해 모든 경우의 수를 탐색합니다.

연산자를 이용해 계산한 값과 현재 몇 번째 연산을 진행하는지에 대한 정수를 메소드 인자로 하여 재귀함수를 작성합니다.

연산자 배열을 탐색하며 값이 존재한다면 해당 연산자로 연산을 수행합니다. 한번 연산을 수행한 연산자는 값을 1 만큼 감소시킵니다.

연산 횟수가 모두 채워진다면, 연산이 끝난 값과 기존에 있던 최대값, 최소값을 비교하여 알맞은 값을 대입합니다.