[백준 / C언어] 14888번: 연산자 끼워넣기 (삼성 SW 기출)

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

14888번: 연산자 끼워넣기

 

난이도: solved.ac 실버 1

 

알고리즘 분류

---

브루트포스 알고리즘, 백트래킹

 

접근 방법

---

N개의 수 사이 N - 1개의 자리에 모두 들어갈 수 있는 N - 1개의 연산자가 주어지고, 연산은 연산자 우선순위를 무시하고 앞에서부터 진행되므로, 직접 다 하나씩 집어넣어보는 브루트포스 알고리즘을 사용한다.

 

구현

---

N개의 수를 저장할 배열 A와 각 연산자의 개수를 저장할 배열 op을 만들었다.

백트래킹 알고리즘을 사용해 op의 원소가 0이 될 때까지 op[i]에서 하나씩 꺼내 앞의 수와 연산을 해주었다.

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
int A[11], op[4];
int N, min = 1000000000, max = -1000000000;
void calculate(int result, int cur);
 
int main() {
	int i;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < 4; i++)
		scanf("%d", &op[i]);
	
	calculate(A[0], 0);
	printf("%d\n%d", max, min);
	return 0;
}
 
void calculate(int result, int cur) {
	if (cur == N - 1) {
		if (result > max)
			max = result;
		if (result < min)
			min = result;
	}
	for (int i = 0; i < 4; i++) {
		if (op[i]) {
			op[i]--;
			if (i == 0)
				calculate(result + A[cur + 1], cur + 1);
			else if (i == 1)
				calculate(result - A[cur + 1], cur + 1);
			else if (i == 2)
				calculate(result * A[cur + 1], cur + 1);
			else if (i == 3)
				calculate(result / A[cur + 1], cur + 1);
			op[i]++;
		}
	}
}