[백준] 16637. 괄호 추가하기

문제

https://www.acmicpc.net/problem/16637

접근 방법

재귀

• 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. << 문제 조건에 주의한다.
  ex. 8*3+5
  = 1. (8*3) + 5
  = 2. 8* (3+5)
  나뉘는 경우가 2가지 경우밖에 없기 때문에 이를 고려하여 재귀를 돌려준다.

말로 풀어서 설명하면
1. (8*3) + 5 = { {0번째 숫자, 1번째 숫자 를 0번째 연산기호로 계산} , 2번째 숫자 를 1번째 연산 기호로 계산 }
2. 8 * (3+5) = { 0번째 숫자 , {1번째 숫자, 2번째 숫자를 1번째 연산기호로 계산} 를 0번째 연산 기호로 계산 }

이를 함수화 하면 아래와 같다.

void Recursive(int idx, int num)
{
	if (idx == numVec.size() - 1) // 마지막 숫자까지 계산된 경우
    {
    	result = max(result, num); // 최댓값 갱신
        return;
    }
    int temp = Calculate(operVec[idx], num, numVec[idx+1]);
    Recursive(idx+1, temp);
   	if (idx+2 <= numVec.size() - 1) // 범위 초과 안되는 선에서
    {
    	int temp = Calculate(operVec[idx+1], numVec[idx+1], numVec[idx+2]);
        Recursive(idx+2, Calculate(operVec[idx], num, temp));
    }
}

풀이

#include <iostream>
#include <vector>

using namespace std;

int N; // 수식의 길이 1 ~ 19 

vector<int> numVec; // 숫자 벡터 
vector<char> operVec; // 연산자 벡터

int result = -987654321;

void FastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void Input()
{
    cin >> N;

    char temp; 
    for(int i=0; i<N; i++)
    {
        cin >> temp;

        // 숫자와 기호 구분하기
        if ('0' <= temp && temp <= '9') 
            numVec.push_back(temp - '0');
        else 
            operVec.push_back(temp);
    }
}

int Calculate(char oper, int a, int b)
{
    if (oper == '+') return a+b;
    else if (oper == '-') return a-b;
    else if (oper == '*') return a*b;
}

void Recursive(int idx, int num)
{
	if (idx == numVec.size() - 1) // 마지막 숫자까지 계산된 경우
    {
    	result = max(result, num); // 최댓값 갱신
        return;
    }
   
    int temp = Calculate(operVec[idx], num, numVec[idx+1]);
    Recursive(idx+1, temp);
   	if (idx+2 <= numVec.size() - 1) // 범위 초과 안되는 선에서
    {
    	int temp = Calculate(operVec[idx+1], numVec[idx+1], numVec[idx+2]);
        Recursive(idx+2, Calculate(operVec[idx], num, temp));
    }
}

void Solve()
{    
    Recursive(0, numVec[0]);

    cout << result;
}

int main()
{
    FastIO();
    Input();
    Solve();
}

정리

조건을 다시 확실하게 보고 풀자..!

참고

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트