BOJ 1541 - 잃어버린 괄호

문제

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

1541번: 잃어버린 괄호

 

 

풀이

55-50+40 에서 55-(50+40)으로 괄호를 씌우면 최소값인 -35가 나오게 된다. 이 때 ()를 전개해서 표현하면 '+' 기호는

'-' 기호로 바뀌어서 55-50-40이 된다. 이 원리를 이용해서 첫 번째 '-' 이후에 나오는 모든 '+' 기호를 '-'로 치환하면 최소값이 나오게 된다. 

 

---

 

1. 첫 숫자부터 -가 나오기 전까지 모든 숫자를 더해준다

2. - 이후 나오는 숫자들은 괄호를 치면 모두 뺄 수 있으므로 모두 빼준다

 

 

코드

C++

#include <iostream>
#include <string>
 
using namespace std;
 
string s;
int index, result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> s;
 
    index = s.size();
    for (int i=0; i<s.size(); i++)
        if (s[i] == '-') 
        {   
            index = i;
            break;
        }
 
    for (int i=index+1; i<s.size(); i++)
        if (s[i] == '+') s[i] = '-';
 
    if (s[0] != '-') s = "+" + s;
 
    int num = 0;
    int temp = 1;
    for (int i=s.size()-1; i>=0; i--)
    {
        if (s[i] == '+') 
        {
            result += num;
            temp = 1;
            num = 0;
        }
        else if (s[i] == '-') 
        {
            result -= num;
            temp = 1;
            num = 0;
        }
        else
        {
            num += (s[i] - '0') * temp;
            temp *= 10;
        }
    }
 
    cout << result;
 
    return 0;
}

 

 

java

import java.util.Scanner;
 
public class Main {
 
    private static String s;
 
    public static void main(String[] args) {
        input();
        solve();
    }
 
    private static void solve() {
        int sum = 0;
 
        String[] a = s.split("-");
 
        for (int i = 0; i < a.length; i++) {
            int part = partSum(a[i]);
            if (i == 0) {
                sum += part;
            } else {
                sum -= part;
            }
        }
 
        System.out.println(sum);
    }
 
    private static int partSum(String string) {
        String[] a = string.split("\\+");
 
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += Integer.parseInt(a[i]);
        }
 
        return sum;
    }
 
    private static void input() {
        Scanner sc = new Scanner(System.in);
        s = sc.next();
    }
 
}
 

 

 

python

answer = 0
 
equation = input().split('-')
 
for num in equation[0].split('+'):
    answer += int(num)
 
for sub_equation in equation[1:]:
    for num in sub_equation.split('+'):
        answer -= int(num)
 
print(answer)