[백준 1541번 : 실버2] 잃어버린 괄호 ( 그리디 / Java)

이번 문제는 생각보다 쉽게 풀수 있는 문제였는데 내가 조금 어렵게 생각해 약간의 힌트(사실상 정답)을 받고

문제를 풀었다.

 

이번 문제는 약간의 수학적인 사고만 있다면 금방 풀수 있는 문제이다.

 

 

그럼 이제 문제를 살펴보자.

 

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

 

 

 

 

문제 접근 방법

이번 문제는 우리가 구해야 할것이 괄호를 잘 사용해서 최소한의 수를 만들어내 출력하는것이다.

 

+와 -가 같이 존재하는곳에서 가장 작은 수를 만들어 내려면 일단 +들끼리 서로 더한 다음

다 빼주는것이 가장 작은 수이다.

 

 

따라서 -로 split을 해주고

+가 있는 애들은 +로 split 해서 안의 값들을 다 더한다.

그리고 나머지를 다 빼주면 된다.

 

따라서 소스를 보면 아래와 같아진다

 

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		
		String sik = sc.next();
//		String sik = "30-70-20+40-10+100+30-35";
		String[] minus = sik.split("-"); //-를 기준으로 나눈다.
		int result = 0;
		for(int i = 0; i<minus.length;i++) {
			//+는 split 할때 에러가 생기므로 \\를 앞에 붙여줘야 한다.
			String[] plus = minus[i].split("\\+"); //-를 기준으로 나눈애들중 +를 기준으로 나눈다.
			int sum = 0;
			//+로 되어 있는애들을 다 더하는 과정
			for(int j = 0;j<plus.length;j++) {
				sum+=Integer.parseInt(plus[j]);
			}
			//처음부터 빼면 안되니 처음엔 그냥 값을 넣어준다.
			if(i == 0)
				result = sum;
			else
				result -=sum;
		}
		System.out.println(result);
	}
}

 

 

느낀점

 

1. 원하는 값을 만들려면 어떻게 해야하는지를 먼저 생각해보자.