백준 16637 괄호 추가하기

아이디어

• 문제의 요소들을 그대로 구현할 줄 안다

접근방식

1. 연산을 string에 넣어준다
2. DFS를 실행한다
3. 괄호를 치지 않는 경우, 해당 숫자와 저장한 숫자(왼쪽부터 연산)에 대한 연산을 진행 후 값을 저장, 다음 숫자에 대해 DFS를 진행한다
4. 괄호를 치는 경우, 해당 숫자와 그 다음 숫자에 대한 연산을 진행 후, 저장한 숫자와 연산한 숫자를 또한번 연산해준다. 그 후 다음 다음 숫자(다음 숫자까지는 연산을 완료했기 때문)에 대해 DFS를 진행한다
5. 현재 위치가 string 길이 이상이면 모든 요소를 연산했다고 판단, answer에 대해 더 큰값이면 갱신해준다.
6. 만약 현재 위치가 string 길이 - 2일경우, 다음 연산은 괄호를 칠 수 없다고 판단, 괄호를 치지 않는 연산만 실행 후 return 해준다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>

using namespace std;

int n;
string s;

long long int answer = -2147483648;

void dfs(long long int now_value, long long int now_pos)
{
	if (now_pos >= n)
	{
		if (answer < now_value) answer = now_value;
		return;
	}

	char now_cal = s[now_pos-1]; //계산하려는 연산자
	long long int now_num = s[now_pos] - '0'; //지금 해당하는 숫자
	long long int new_non_value;

	//만약 괄호를 안친다면 now_value에 연산을 하고 보냄

	if (now_cal == '+') new_non_value = now_value + now_num;
	else if (now_cal == '-')  new_non_value = now_value - now_num;
	else new_non_value = now_value * now_num;

	dfs(new_non_value, now_pos + 2);

	//만약 마지막 숫자라면? 여기서 끝냄 더이상 괄호 칠 수 없음
	if (now_pos == n - 1) return;

	//만약 괄호를 친다면, 3개를 모두 연산 후 now_value와 연산, 그리고 다음 연산자를 골라둠
	long long int now_sec_num = s[now_pos + 2] - '0';
	long long int sec_value;
	char between_cal = s[now_pos + 1];

	if (between_cal == '+') sec_value = now_num + now_sec_num;
	else if (between_cal == '-')  sec_value = now_num - now_sec_num;
	else sec_value = now_num * now_sec_num;

	if (now_cal == '+') new_non_value = now_value + sec_value;
	else if (now_cal == '-')  new_non_value = now_value - sec_value;
	else new_non_value = now_value * sec_value;

	dfs(new_non_value, now_pos + 4);


}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	
	//짝수 == 숫자, 홀수 == 연산자
	
	cin >> n >> s;

	long long int first_value = s[0] - '0';
	
	if (s.size() == 1)
	{
		cout << s[0] << endl;
		return 0;
	}

	char between_cal = s[1];
	long long int second_value = s[2] - '0';

	long long int calculated_value = 0;

	if (between_cal == '+') calculated_value = first_value + second_value;
	else if (between_cal == '-') calculated_value = first_value - second_value;
	else if (between_cal == '*') calculated_value = first_value * second_value;

	if (s.size() == 3)
	{
		cout << calculated_value << endl;
		return 0;
	}

	//첫괄호를 안쳤을 때
	dfs(first_value, 2);

	//첫 괄호 쳤을때
	dfs(calculated_value, 4);

	cout << answer;


	return 0;
}

평가

DFS 라기 보다는 시뮬레이션? 에 가까운 문제.
왼쪽부터 계산을 하기에, 정확한 구현만 할 수 있다면 어렵지 않은 문제였습니다. 하지만 다른 풀이를 보니 +,-,*에 대한 연산을 함수를 따로 생성하여 calling을 통해 연산하는 풀이가 있었습니다. 모든 연산을 직접 코드에 넣다보니 저의 코드가 많이 지저분 하다는 걸 알 수 있었습니다.

• 배울 것
  1) 반복되는 코드가 실행 될 경우, 함수를 따로 생성하면 코드가 더 심플해질 수 있다.