[파이썬, 자바] 백준 - 1541 (그리디 알고리즘)

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

 

+와 -로만 이루어져 있는 식을 최소로 만드려면 빼야할 값을 최대한 키워서 빼면 된다.

 

<계산 순서>

1. -를 기준으로 식 슬라이싱

2. 분해된 부분식 덧셈 연산

3. 연산된 결과값 뺄셈 연산

 

풀이법을 생각해내기만 한다면, 문자열 슬라이싱으로 해결할 수 있는 문제이다.

 

Code(Python)

import sys
input = sys.stdin.readline

def cal(li): # 부분식 연산 함수
    li = li.split('+') # 부분식을 + 기준으로 슬라이싱

    subSum = 0 # 부분합
    for num in li: # 슬라이싱된 문자들
        subSum += int(num) # 숫자로 바꿔서 덧셈

    return subSum # 부분합 반환

exp = input().rstrip().split('-') # 입력받은 식을 - 기준으로 슬라이싱

result = 0 # 결과값
for i in range(len(exp)):
    if i == 0: # 맨 처음 연산 결과는 더해줘야 한다.
        result += cal(exp[i])
    else:
        result -= cal(exp[i]) # 나머지 연산 결과는 모두 빼기

print(result)

 

Code(Java)

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[] subExp = br.readLine().split("-");

        int result = 0;
        for (int i = 0; i < subExp.length; i++) {
            if (i == 0) {
                result += cal(subExp[i]);
            } else {
                result -= cal(subExp[i]);
            }
        }
        System.out.println(result);
    }

    private static int cal(String s) {
        String[] li = s.split("\\+"); // +는 정규표현식에 사용되는 문자이기 때문에 그대로 사용하면 안 된다.(\\+ or [+] 사용)
        int subSum = 0;
        for (String num : li) {
            subSum += Integer.parseInt(num);
        }

        return subSum;
    }
}