문제

문제 링크

해설

문제 함정

• 이 문제가 대표적인 ‘조합’으로 풀려고 할 때 함정에 빠지는 문제입니다.
• 아마 조합으로 풀려고 하셨던 분들께서는, 각 연산자에 번호를 할당하고 괄호가 0개, 1개, 2개, … , ceil(N / 2)개 인 경우에 대해 조합을 구하려고 하셨을 것 같습니다.
• 그리고 괄호는 겹칠 수 없기 때문에 선택된 숫자들은 연속해선 안됩니다.
• 그리고 왼쪽 → 오른쪽으로 계산해야 하므로 각 조합은 오름차순으로 구해야 합니다.
• 예를 들어
  • N = 9 일 때 연산자에 번호를 할당하면 {1, 2, 3, 4}가 나오므로
    • 괄호가 없는 경우 → {1, 2, 3, 4}
    • 괄호가 1개 있는 경우 → {1 | 2, 3, 4}, {2 | 1, 3, 4}, {3 | 1, 2, 4}, {4 | 1, 2, 3}
    • 괄호가 2개 있는 경우 → {1, 3 | 2, 4}, {1, 4 | 2, 3}, {2, 4 | 1, 3}
    • 이렇게 총 8가지 경우가 나옵니다.
  • N = 11 일 때 연산자에 번호를 할당하면 {1, 2, 3, 4, 5}가 나오므로
    • 괄호가 없는 경우 → {1, 2, 3, 4, 5}
    • 괄호가 1개 있는 경우 → {1 | 2, 3, 4, 5}, {2 | 1, 3, 4, 5}, {3 | 1, 2, 4, 5}, {4 | 1, 2, 3, 5}, {5 | 1, 2, 3, 4}
    • 괄호가 2개 있는 경우 → {1, 3 | 2, 4, 5}, {1, 4 | 2, 3, 5}, {1, 5 | 2, 3, 4}, {2, 4 | 1, 3, 5}, {2, 5 | 1, 3, 4}, {3, 5 | 1, 2, 4}
    • 괄호가 3개 있는 경우 → {1, 3, 5 | 2, 4}
    • 이렇게 총 12가지 경우가 나옵니다.
  • 대충 보면 아시겠지만, 이걸 next_permutation() 함수 또는 다른 방법을 이용해서 구하는 게 절대 쉽지 않습니다.

문제 해설

• 우선, 함정 때와 동일하게 숫자와 연산자를 분리해야 한다는 점은 동일합니다.
• 위 그림을 보면, N = 5일 때부터 두 가지 경우의 수가 생깁니다.
  • 가장 앞쪽 숫자를 idx번째 숫자라고 가정하겠습니다.
  • 첫 번째 경우의 수
    • idx번째 숫자와 idx + 1번째 숫자를 idx번째 연산자로 연산합니다.
    • 그 결과값과 idx + 2번째 숫자를 idx + 1번째 연산자로 연산합니다.
  • 두 번째 경우의 수
    • idx + 1번째 숫자와 idx + 2번째 숫자를 idx + 1번째 연산자로 연산합니다.
    • 그 결과값과 idx번째 숫자를 idx 번째 연산자로 연산합니다.
• 즉, 전자는 괄호가 없는 경우와 앞쪽에 괄호가 있는 경우를 의미하고,
  후자는 뒤쪽에 괄호가 있는 경우를 의미합니다.
• N = 7, 9, 11 이렇게 가더라도 결국은 위 과정이 부분문제이므로 재귀함수를 이용할 수 있다는 것을 알 수 있습니다.
• 모든 숫자에 대해 계산을 마쳤을 때 그 결과값 중 가장 큰 값을 반환하면 됩니다.

코드

#include <iostream>
#include <vector>
using namespace std;

int N, answer = -1e9;
vector<int> operands;
vector<char> operators;

inline int calc(char op, int lhs, int rhs) {
    if (op == '+') return lhs + rhs;
    if (op == '-') return lhs - rhs;
    return lhs * rhs;
}

void solve(int idx, int sum) {
    if (idx == operands.size() - 1) { answer = max(answer, sum); return; }
    solve(idx + 1, calc(operators[idx], sum, operands[idx + 1]));
    // 만일 다다음 숫자가 있어서, 다른 경우의 수를 고려할 수 있다면
    if (idx < operands.size() - 2)
        solve(idx + 2, calc(operators[idx], sum, calc(operators[idx + 1], operands[idx + 1], operands[idx + 2])));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; i++) {
        char ch;
        cin >> ch;
        (i & 1) ? operators.push_back(ch) : operands.push_back(ch - '0');
    }
    // 첫 번째 수가 바로 sum으로 들어가는 것을 주의하세요.
    solve(0, operands[0]);
    cout << answer << '\n';
    return 0;
}

소스코드 링크

• answer 초기값이 -1e9임을 주의하세요.
• 이 문제는 답이 음수가 나올 수 있기 때문에 초기값을 0으로 설정하면 안 됩니다.

결과