백준 14888번 연산자 끼워넣기

문제링크

문제 해설

접근법

일단 n의 범위가 11까지다. 따라서 연산자의 개수는 10까지만 가능하다.

게다가 연산자의 종류는 4개이므로 최소 1가지는 2개 이상이다.

따라서 연산자 순서의 가능한 경우는 10!보다 작을 수 밖에 없다.

게다가 10!은 10의 8제곱보다 작으므로 제한시간인 1초 내에 계산 완료 할 수 있다.

따라서 브루트 포스로 계산하였다.

풀이

풀이는 간단하다.

1. 재귀 호출
2. 재귀 호출 회수가 n번과 같다면 연산자를 모두 사용했으므로 배열에 저장.
3. 배열을 정렬해서 최소, 최대 값 찾기. (정렬에 시간이 좀 더 사용되긴 한다.)

소스코드

#include <iostream>
#include <vector>
#include <algorithm>

// 백준 14888번 연산자 끼워넣기

using namespace std;

// 최대 10!가지라서 브루트포스 => 재귀 이용.
// n번 다 돌았으면 배열에 넣어주고 sort. 최대값 최소값 출력.

int n;
int arr[11];
vector<int> ans;

int notice(int idx, int val, int operand) {
	switch (idx) {
	case 0: return val + operand;
	case 1: return val - operand;
	case 2: return val * operand;
	case 3: return val / operand;
	}
}

void count(int cnt, int val, vector<int> op) {
	if (cnt == n) {
		ans.push_back(val);
		return;
	}
	int operand = arr[cnt];
	for (int i = 0; i < 4; i++) {
		if (op[i] > 0) {
			int new_val = notice(i, val, operand);
			op[i]--;
			count(cnt + 1, new_val, op);
			op[i]++;
		}
	}
	
	return;
}

int main() {
	cin >> n;
	vector<int> op(4, 0);

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < 4; i++)
		cin >> op[i];
	count(1, arr[0], op);
	sort(ans.begin(), ans.end());

	cout << ans[ans.size() - 1] << endl;
	cout << ans[0] << endl;

	return 0;
}

그 외

비슷하다고 생각했던 문제

프로그래머스 -타겟넘버