[Programmers] 사칙연산

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/1843

코딩테스트 연습 - 사칙연산

분할 정복과 DP 알고리즘을 조합한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. A 구간과 B 구간 사이의 연산자가 +라면 A 구간 내 연산 결과 중 최댓값과 B 구간 내 연산 결과 중 최댓값을 더해야 최댓값을 구할 수 있습니다.

1.1 A 구간과 B 구간 사이의 연산자가 -라면 A 구간 내 연산 결과 중 최대값과 B 구간 내 연산 결과 중 최솟값을 더해야 최댓값을 구할 수 있습니다.

2. 따라서, dp를 이용해 구간 내 연산 결과 최대, 최소값을 구해줍니다.

3. 2번에서 구한 결과를 토대로 구간 내 최대값을 반환해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	const int INF = 987654321;
	const int MAX = 200 + 20;
	int cache[MAX][MAX][2];
	vector<int> numbers;
	vector<string> ops;
	void init(vector<string> arr)
	{
	for (int i = 0; i < arr.size(); i++)
	{
	if (i % 2 == 0)
	{
	numbers.push_back(stoi(arr[i]));
	}
	else
	{
	ops.push_back(arr[i]);
	}
	}
	}
	int func(int start, int end, bool isMax)
	{
	int &result = cache[start][end][isMax];
	if (result != -1)
	{
	return result;
	}
	if (start == end)
	{
	return result = numbers[start];
	}
	result = isMax ? -INF : INF;
	for (int i = start; i < end; i++)
	{
	if (ops[i] == "-")
	{
	result = isMax ?
	max(result, func(start, i, true) - func(i + 1, end, false)) :
	min(result, func(start, i, false) - func(i + 1, end, true));
	}
	else
	{
	result = isMax ?
	max(result, func(start, i, true) + func(i + 1, end, true)) :
	min(result, func(start, i, false) + func(i + 1, end, false));
	}
	}
	return result;
	}
	int solution(vector<string> arr)
	{
	init(arr);
	memset(cache, -1, sizeof(cache));
	return func(0, arr.size() / 2, true);
	}
	int main(void)
	{
	vector<string> arr = { "1", "-", "3", "+", "5", "-", "8" };
	cout << solution(arr) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~