백준 14888 - 연산자 끼워넣기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

삼성 SW 역량테스트 기출문제입니다.

모든 경우를 확인하면 풀 수 있는 문제였습니다.

문제 조건

출력 예시

N값과 나올 수 있는 경우가 적기에 모든 경우를 확인해보면 됩니다.

 

 

1. 경우 확인하기

void dfs_calculation(int plus, int minus, int multi, int divide, int cnt, int sum) {
	if (cnt == N) {
		maxi = max(maxi, sum);
		mini = min(mini, sum);
	}
	else {
		if (plus > 0) {
			dfs_calculation(plus - 1, minus, multi, divide, cnt + 1, sum + num[cnt + 1]);
		}
		if (minus > 0) {
			dfs_calculation(plus, minus - 1, multi, divide, cnt + 1, sum - num[cnt + 1]);
		}
		if (multi > 0) {
			dfs_calculation(plus, minus, multi - 1, divide, cnt + 1, sum * num[cnt + 1]);
		}
		if (divide > 0) {
			dfs_calculation(plus, minus, multi, divide - 1, cnt + 1, sum / num[cnt + 1]);
		}
	}
}

각각 plus, minus, multi, divide 값이 1 이상이라면 해당 연산을 할 수 있다는 의미입니다.

따라서 해당 연산을 했을 경우를 확인해줍니다. 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N;
int num[12];
int calculation[4]; // +, - , *, /
int maxi = -111111111, mini = 1111111111;

void dfs_calculation(int plus, int minus, int multi, int divide, int cnt, int sum) {
	if (cnt == N) {
		maxi = max(maxi, sum);
		mini = min(mini, sum);
	}
	else {
		if (plus > 0) {
			dfs_calculation(plus - 1, minus, multi, divide, cnt + 1, sum + num[cnt + 1]);
		}
		if (minus > 0) {
			dfs_calculation(plus, minus - 1, multi, divide, cnt + 1, sum - num[cnt + 1]);
		}
		if (multi > 0) {
			dfs_calculation(plus, minus, multi - 1, divide, cnt + 1, sum * num[cnt + 1]);
		}
		if (divide > 0) {
			dfs_calculation(plus, minus, multi, divide - 1, cnt + 1, sum / num[cnt + 1]);
		}
	}
}

void solve() {
	dfs_calculation(calculation[0], calculation[1], calculation[2], calculation[3], 1, num[1]);
	cout << maxi << "\n" << mini;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> num[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> calculation[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!