백준 1541 - 잃어버린 암호 [자바]

* 개인적인 기록용입니다.

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

 

왜 그리디인가?

‘+’와 ‘-‘ 그리고 ‘수’로 구성된 식이 있을 때 그 식을 최소로 만드는 계산법을 찾는 것인데, 만약 식에서 ‘-‘를 빼는 것으로 생각하면 ‘-‘ 식 계산 후에 더하는 식이 또 있다면 필연적으로 결과값이 점점 커지게 됩니다. 그래서 최솟값이 절대 될 수 없습니다.

 

하지만 ‘-‘를 음수로 바꾸는 것으로 생각한다면 ‘-‘ 뒤의 더하는 식들을 이용하여 최솟값을 만들 수 있게 됩니다! 즉, 음수는 절댓값이 클수록 더 작은 값임을 이용하는 것이죠. 예를 들어, 10+20-30+40+50+60-70과 같은 식이 있다면 다음과 같이 묶어주어 10+20-(30+40+50+60)-70 계산하면 최솟값이 됨을 알 수 있습니다.

 

정리하자면 최대한 많은 수를 더해서(탐욕) 음수로 만들면 그 값이 최솟값이 되는 것입니다.

 

 

코드

// 그리디 - boj.kr/1541 잃어버린 괄호
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1541 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String exp = br.readLine();
        String[] exps;
        int sum = 0;

        exps = exp.split("\\-");

        for (int i = 0; i < exps.length; i++) {
            int add = 0;
            for (String s : exps[i].split("\\+"))
                add += Integer.parseInt(s);

            if (i > 0)
                sum += (-add);
            else
                sum += add;
        }

        System.out.println(sum);
    }
}