[BOJ] 백준 14888 연산자 끼워넣기 간단한설명과 코드 C++

09 Jan 2020

Reading time ~1 minute

문제 정보

백준 ( BOJ ) 14888 연산자 끼워넣기

문제 풀이 : 순열 프로그래밍

문제 출처 : https://www.acmicpc.net/problem/★

시작 Thinking

문제 풀이

미리 고려할 것을 생각하면 구현만 하면 됩니다.

순열은 정말 다양한 문제에서 활용되기 때문에,

구현하는 방법을 다들 아실 거 같지만,

그래도 구현하는 방법으론, 가장 기본적으로 재귀 방식이 있습니다.

예를들어 a 3개, b2개 c2개로 가능한 모든 조합을 뽑으려면 어떻게 해야 할까요?

수도코드로 한번 알아보겠습니다.

 재귀함수(){
 if ( a갯수 > 0 )
  a갯수-
  재귀함수( 문장+a , 갯수 배열(혹은백터) , 총 갯수) 
  a갯수 +
  }
  ... (b,c 도 같은구조)
  }

이렇게 하나하나 더해가면 모든 경우의 수를 다 돌 수 있습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int resultMax = -1000000000;
int resultMin = 1000000000;
vector<int> numbers(n);

void fun(int k, vector<int> cal, int tempResult) {
	if (k == n) {
		if (tempResult > resultMax) {
			resultMax = tempResult;
		}
		if (tempResult < resultMin) {
			resultMin = tempResult;
		}
	}

	else {
		if (cal[0] > 0) {
			cal[0] --;
			fun(k + 1, cal, tempResult + numbers[k]);
			cal[0]++;
		}
		if (cal[1] > 0) {
			cal[1] --;
			fun(k + 1, cal, tempResult - numbers[k]);
			cal[1]++;
		}
		if (cal[2] > 0) {
			cal[2] --;
			fun(k + 1, cal, tempResult * numbers[k]);
			cal[2]++;
		}
		if (cal[3] > 0) {
			cal[3] --;
			fun(k + 1, cal, tempResult / numbers[k]);
			cal[3]++;
		}
	}
}


int main() {
	vector<int> cal(4);
	int temp;
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		numbers.push_back(temp);
	}

	for (int i = 0; i < 4; i++) {
		cin >> temp;
		cal[i] = temp;
	}

	fun(1, cal, numbers[0]);
	
	cout << resultMax << "\n" << resultMin;
  
	return 0;
}

문제 후기

소요 시간 : 25분

틀린 횟수 : 0번

발생 에러 : 없음

백준 C++순열