백준 14888. 연산자 끼워넣기 - 문제풀이 (c++) (순열, 완전탐색)

🔎 14888. 문제 보기

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

---

💡 문제 풀기 전

처음에 문제를 잘못 봐서 연산자 우선순위를 무시하는지 모르고 헤맸다. 근데 다시 읽어보니 연산자 우선순위를 무시하고 앞에서부터 계산하는 것을 보고 순열, 완전탐색이라는 것을 깨달았다.

---

📝 코드 보기

1. pos를 이용한 순열

#include <bits/stdc++.h>
using namespace std;

int arr[12];
int oper[12];
int ret[12];
int check[12];

int n, m, mx=-1000000000, mn=1000000000;
void f(int pos) {
	if(pos==n) {
		int sum=arr[0], index=0;	
		for(int i=1; i<=m; i++) {				
			if(ret[i]==0) {
				sum+=arr[i];
			} else if(ret[i]==1) {
				sum-=arr[i];
			} else if(ret[i]==2) {
				sum*=arr[i];
			} else {
				sum/=arr[i];
			}
		}	
		if(sum>mx) mx=sum;
		if(sum<mn) mn=sum; 
		return;
	}
	
	for(int i=0; i<m; i++) {
		if(check[i]==1) continue;
		check[i]=1;
		ret[pos]=oper[i];
		f(pos+1);
		check[i]=0;
	}
}

int main() {
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> arr[i];		
	}
	m=n-1;
	
	int oper_cnt, cnt=0;
	for(int i=0; i<4; i++) { // i=0 (+), i=1 (-), i=2 (*), i=3 (/)
		cin >> oper_cnt;
		for(int j=0; j<oper_cnt; j++) {
			oper[cnt]=i;
			cnt++;
		}
	}
	f(1);
	
	cout << mx << "\n" << mn;
	return 0;
}

---

2. 완전 탐색 재귀

#include <bits/stdc++.h>
using namespace std;

int arr[12];
int oper[12];
int mx=-1000000000, mn=1000000000;
int n;

void f(int plus, int minus, int multi, int divide, int cnt, int sum) {
	if(cnt==n) {
		mx=max(mx, sum);
		mn=min(mn, sum);
	}

	if(plus>0) {
		f(plus-1, minus, multi, divide, cnt+1, sum+arr[cnt]);
	}
	if(minus>0) {
		f(plus, minus-1, multi, divide, cnt+1, sum-arr[cnt]);
	}
	if(multi>0) {
		f(plus, minus, multi-1, divide, cnt+1, sum*arr[cnt]);
	}
	if(divide>0) {
		f(plus, minus, multi, divide-1, cnt+1, sum/arr[cnt]);
	}
}

int main() {

	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> arr[i];
	}
	
	for(int i=0; i<4; i++) {
		cin >> oper[i];
	}
	
	f(oper[0], oper[1], oper[2], oper[3], 1, arr[0]);
	
	cout << mx << endl << mn;
	return 0;
}

🎈 코드 풀이 및 관련 개념

1. POS를 이용한 순열

순열을 내가 직접 만들어줬다 예를 들어 (+)는 2개, (-)는 1개가 있으면 순열은
++-, +-+, -++이렇게 있다. 즉 이미 부호를 썼을 경우에는 부호를 썼다는 의미의 check배열을 이용해 부호 중복을 방지했다. => N과M문제들과 유사

---

2. 완전 탐색 재귀

각 각의 부호 숫자를 하나씩 줄여가면서 다음 값과 부호를 비교해 연산해준다.