<C++/백준 16637> 괄호 추가하기

🥇 골드 3

📌 문제 패턴 인식

연산자가 등장할 때마다 2가지 선택(괄호 유무)이 가능하고, 이전까지의 계산 결과를 기반으로 다음 선택을 해야 하는 유형

🔍 특징

수식에서 ”누적되는 값 + 다음 선택” 형태

psum(prefix_sum, 누적합 문제!)

괄호 위치 결정 문제
매 시점 2가지 선택 가능

💡 핵심 아이디어

1. 누적값 + 방향 결정

지금까지의 계산 결과를 가지고
다음에 어떤 연산을 할지 결정! (재귀함수)
go(위치, 누적값) 형태로 구현

2. 매 시점 2가지 선택

괄호 없이 그냥 계산
다음 두 수를 묶어서 계산 (인덱스 주의)

🔨 코드 구현

기본 뼈대

void go(int here, int sum) {
    // 1. 끝에 도달
    if(here == 마지막) {
        ret = max(ret, sum);
        return;
    }
    
    // 2. 괄호 없이 계산
    go(here + 1, 계산결과);
    
    // 3. 괄호 사용해서 계산
    if(다음숫자가_2개이상_남았으면) {
        go(here + 2, 계산결과);
    }
}

주요 자료구조

vector<int> num;        // 숫자 저장
vector<char> oper_str;  // 연산자 저장

🎯 문제 해결 접근법

1. 첫 번째 단계

“누적값 + 선택” 패턴 인식하기
go(위치, 누적값) 형태 떠올리기

2. 두 번째 단계

매 위치에서 가능한 선택지 정리
재귀로 모든 경우 탐색

👀 비슷한 문제 패턴

수식 계산 + 괄호 추가/삭제
매 시점 2가지 이상 선택지
이전 결과로 다음 선택하는 경우

📝 예시 입출력

입력: 3+8*7
출력: 77

경로1: 3+8*7 = 11*7 = 77
경로2: 3+(8*7) = 3+56 = 59

⚠️ 주의사항

인덱스 범위 체크 필수
괄호 안에는 연산자 하나만
중첩된 괄호 불가능

정답 코드 (디버깅 코드 포함)


#include <bits/stdc++.h>
using namespace std;


// 숫자와 연산자를 따로 저장할 벡터
vector<int> num;    // 숫자만 저장하는 벡터 (ex: "3+8*7" => {3, 8, 7}
vector<char> oper_str;  // 연산자만 저장하는 벡터 (ex: "3+8*7" => {'+', '*'}

// 전역 변수 선언
int n;
int ret = INT_MIN;  // 최댓값을 저장할 변수 (충분히 작은 값으로 초기화)
string s;

// 연산을 수행하는 함수
// a: 연산자
// b, c: 피연산자 (숫자)
int oper(char a, int b, int c) {
    cout << "연산 수행: " << b << a << c << "=";
    int result;
    if(a == '+') result = b + c;
    if(a == '-') result = b - c;
    if(a == '*') result = b * c;
    cout << result << '\n';
    return result;
}


// 재귀적으로 모든 경우를 탐색하는 함수
// here: 현재 보고 있는 연산자의 위치
// _num: 현재까지 계산된 결과
void go(int here, int _num) {
    cout << "\n현재 위치(here): " << here << ", 현재까지의 계산값(_num): " << _num << '\n';
    
    // 기저 사례: 마지막 숫자까지 왔을 때
    if(here == num.size() - 1) {
        cout << "끝에 도달! 현재 ret: " << ret << ", 새로운 값: " << _num << "\n";
        ret = max(ret, _num);
        return;
    }
    
    // 1. 괄호 없이 순서대로 계산하는 경우
    cout << "괄호 없이 계산하는 경우, go(" << here + 1 << ", oper(" << oper_str[here] << ", " << _num << ", " << num[here + 1] << ")) 호출\n";
    go(here + 1, oper(oper_str[here], _num, num[here + 1]));
    
    // 2. 다음 두 숫자를 괄호로 묶어서 계산하는 경우
    if(here + 2 <= num.size() - 1) {    // 단, 앞으로 숫자가 2개 이상 남아있어야 함
        cout << "괄호 사용하는 경우\n"; // 디버깅
        cout << "괄호 안을 먼저 계산: " << num[here + 1] << oper_str[here + 1] << num[here + 2] << '\n';
        
        // 괄호 안 계산을 먼저 수행
        int temp = oper(oper_str[here + 1], num[here + 1], num[here + 2]);
        
        // 괄호 계산 결과와 현재까지의 값을 연산
        go(here + 2, oper(oper_str[here], _num, temp));
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s;
    // 수식 문자열에서 숫자와 연산자를 분리하여 저장
    for(int i = 0; i < n; i++) {
        // 짝수 인덱스: 숫자
        if(i % 2 == 0) {
            num.push_back(s[i] - '0');  // 문자를 숫자로 변환하여 저장
        } else {    // 홀수 인덱스: 연산자
            oper_str.push_back(s[i]);
        }
    }
    
    // 계산 시작 (첫 번째 숫자를 초기값으로)
    cout << "\n 계산 시작: \n";
    go(0, num[0]);
    
    // 결과 출력
    cout << "\n최종 결과: " << ret << '\n';
    return 0;
}