• Home
  • About
    • Dochoi의 소소한 코딩 모음 photo

      Dochoi의 소소한 코딩 모음

      코딩을 하면서 느낀점들을 모은 공간입니다.

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • AI
    • Algorithm
    • Algorithm-Test
    • Cloud
    • Docker
    • Kubernetes
    • iOS
    • Culture
  • Projects

[백준] : 15659(연산자 끼워넣기(3))

16 Jun 2020

Reading time ~2 minutes

algorithm-test

15659(연산자 끼워넣기(3))

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <math.h>

using namespace std;
int N;
int A[11] = { 0 };
int O[4] = { 0 };// + - * /
int max_answer = -2147483647;
int min_answer = 2147483647;
vector<int> A_2;
vector<int> O_2;
vector<int> v;
int	main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < 4; i++)
		cin >> O[i];
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < O[i]; j++)
			v.push_back(i);
	do {
		A_2.clear();
		O_2.clear();
		int temp = 0;
		int flag = 0; // 곱셈 덧셈 플래그
		int i = 0;
		temp = A[0];
		while (i < N - 1)
		{
	
			if (!flag)
				temp = A[i];
			if (v[i] < 2)
			{
				if (flag)
					A_2.push_back(temp);
				else
					A_2.push_back(A[i]);
				O_2.push_back(v[i]);
				flag = 0;
			}
			else
			{
	
				if (v[i] == 2)
					temp *= A[i + 1];
				else
					temp /= A[i + 1];
				flag = 1;
			}
			i++;
		}
		if (v[N - 2] < 2)
		{
			A_2.push_back(A[N-1]);
		}
		else
		{
			A_2.push_back(temp);
		}

		int answer = A_2[0];
		for (int i = 0; i < O_2.size(); i++)
		{

			if (O_2[i] == 0) // 연산자가 +이면
				answer += A_2[i + 1];
			else if (O_2[i] == 1) // 연산자가 -이면
				answer -= A_2[i + 1];
		}
		max_answer = max(max_answer, answer);
		min_answer = min(min_answer, answer);
	} while (next_permutation(v.begin(), v.end()));
	cout << max_answer << "\n" << min_answer;
}

고찰

문제는 간단하다 숫자 사이에 +, -, * ,/를 끼워넣어 최댓값 최솟값을 구하는것이다. 하지만 연산자 우선순위를 두어 *, /이 +, - 보다 연산되도록 한다. 우선 next_permutation으로 모든 조합의 연산자 순서를 정하고, *와 /를 먼저 계산하여 남은 연산자와, 새롭게 계산된 숫자를 새로운 각각 새로운 벡터에 넣는다. 그리고 남은 +,-를 계산하여 구현하였다. 생각보다 시간복잡도는 오래 걸리지 않았다, 하지만 구현과정이 까다로웠다. 특히 연산자 우선순위를 넣는부분에서 시간이 오래 걸렸다.



Algorithm-TestBOJImplement Share Tweet +1