[그리디] 백준 - 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

-문제해설

아래 블로그를 참고했다.

https://st-lab.tistory.com/148

 

입력되는 식에서 가장 최솟값을 만들기 위해서는 덧셈 식을 먼저 계산하고 해당 덧셈값을 빼주면 된다.

이렇게 되면 가장 큰 값을 빼게 되므로 최솟값이 나오게 된다.

 

따라서 먼저 -로 식을 분리한다.

-로 분리된 식에서 +로 또 분리한다.

+로 분리된 식을 모두 더한다. (tmp에 저장)

최종결과값이 min에서 덧셈값인 tmp를 빼준다.

 

 

 

 

-자바

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ1541 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int min = Integer.MAX_VALUE;
		//먼저 뺄셈으로 식을 분리한다.
		StringTokenizer st = new StringTokenizer( br.readLine(), "-" );
		
		while( st.hasMoreTokens() ) {
			int tmp = 0;
			
			//뺄셈으로 분리한 식에서 덧셈으로 나누고 덧셈값을 tmp에 저장한다.
			StringTokenizer st2 = new StringTokenizer( st.nextToken(), "+" );
			while( st2.hasMoreElements() ) {
				tmp += Integer.parseInt( st2.nextToken() );
			}
			
			//min에서 덧셈값인 tmp를 빼준다.
			if( min == Integer.MAX_VALUE ) min = tmp;
			else min -= tmp;
		}
		System.out.println( min );
	}
}

 

-파이썬

from sys import stdin
input = stdin.readline
spli = input().rstrip().split( "-" )
mmin = sum( list( map(int, spli[0].split( "+" )) ) )
for i in range( 1, len(spli) ):
    mmin -= sum( list( map(int, spli[i].split( "+" )) ) )
print( mmin )