[C++] 백준 1541번 잃어버린 괄호

1. 문제이해

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

1541번: 잃어버린 괄호

 

주어진 식에 괄호를 적절히 사용하여 식의 값의 최소값을 구하는 것이 목표이다.

단, 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.

또한, 연속해서 두 개 이상의 연산자는 나타나지 않는다.

 

 

 

2. 문제풀이

 

괄호를 적절히 사용하여 식의 값을 최소로 만드는 문제이다.

주어진 식은 모두 숫자와 ‘+’,  ‘-’ 로만 이루어져있다.

여기서, 식의 값을 최소로 만들기 위해서는  ‘-’ 뒤의 문자들을 모두  ‘-’ 로 바꿔주면 된다.

아래 예제를 통해 자세히 알아보자.

 

예제 입력 1을 보면, 주어진 식은 55 - 50 + 40 이다.

해당 식의 값이 최소가 되는 경우는,

55 - (50 + 40) = 55 - 50 - 40 = -35

의 경우이다.

괄호를 통해 ‘-’  뒤의 ‘+’를 ‘-’ 로 만들어 줌으로서, 더 작은 값을 도출하도록 했다.

 

다른 경우인 55 - 50 + 40 + 30 - 20 + 10 의 경우도 보자.

해당 식의 값이 최소가 되는 경우는

55 - (50 + 40 + 30) - (20 + 10) = -95

의 경우이다.

해당 경우 또한, 괄호를 통해 ‘-’  뒤의 ‘+’를 최대한 많이 ‘-’ 로 만들어 줌으로서,

더 작은 값을 도출하도록 했다.

 

 

즉, 괄호를 통해 ‘-’ 뒤의 숫자들과 문자를 묶어줌으로써,

‘+’ 연산을 ‘-’로 바꾸고, 해당 값을 빼주어 식의 값을 최소로 만들면 된다.

즉, ‘-’ 뒤의 숫자들은 모두 빼주기만 하면 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <string>
using namespace std;

int main() {
	string ex;                   // 입력받을 식
	bool check = false;          // - 판별
	string number = "";          // 식에 사용된 숫자
	int min_answer = 0;          // 식의 최솟값

	cin >> ex;

	for (int i = 0; i <= ex.size(); i++) {
		// 1. 기호를 만났거나, 식이 끝났을 시
		if (ex[i] == '-' || ex[i] == '+' || i == ex.size()) {  

			// 앞서 '-'가 있었다면, 숫자를 빼줌
			if (check == true) {    
				// 문자열 형태의 숫자를 정수형으로 변환
				min_answer -= stoi(number);    
				// 사용된 숫자는 공백으로 초기화
				number = "";                    

			}

			// 앞서 '-'가 없었다면, 숫자를 더해줌
			else if (check == false) {
				min_answer += stoi(number);
				number = "";

			}

		}


		// 2. 기호가 아닌 경우 (숫자인 경우)
		else {
			number += ex[i];     // 문자열 형태로 숫자 저장
		}


		// 3. '-'를 만난 경우
		/* 
		해당 구문을 for문의 가장 마지막에 둔 이유는, 
		해당 구문이 앞에 있을 경우 '-' 앞의 숫자부터 빼주게 되기 때문이다.
		예를 들어, 55 - 50 + 40 의 경우, 55 - (50 - 40) 을 해주어야 한다.
		만약, 이 구문을 앞에 두게 되면,
		1의 첫번째 경우를 따르게 되고 앞서 저장되어있던 숫자인 55를 빼주게 된다.
		따라서, -55 - 50 - 40 = -135 라는 결과가 나오게 된다.
		이러한 경우를 방지하기 위해 해당 구문을 가장 아래에 배치하였다.
		*/

		if (ex[i] == '-') {      // - 발견 시, true로 변경
			check = true;
		}

	}

	cout << min_answer;

	return 0;
}

2. 문제풀이에서 도출한 알고리즘을 통해 풀이한 코드는 다음과 같다.

문자열 형태로 식을 입력받은 후, for문을 통해 해당 식을 처음부터 탐색, 연산한다.

 

1. 만약 기호를 만난 경우이거나, 식이 끝난 경우

bool check 값이 true라면, 앞서 '-'가 존재한 것이므로, 이어지는 숫자는 모두 빼준다.

check 값이 false라면, 앞서 '-'가 존재하지 않은 것이므로, 숫자를 더해주면 된다.

(bool check는 '-' 연산자가 있는지를 체크하는 변수이다.)두 경우 모두,

숫자를 사용한 후에는 숫자를 저장하는 변수인 number를 공백으로 초기화해준다.

 

2. 기호를 만나지 않은 경우, 즉 숫자인 경우

number라는 string형 변수에 숫자를 하나씩 연결한다.

(이후 해당 숫자는 연산자를 만나면 stoi를 통해 정수형으로 변환 후 연산하게 된다.)

 

3. '-'를 만난경우

주석에도 자세히 적어놓았지만, 무조건 for구문의 가장 마지막에 위치해야하는 구문이다.

(자세한 설명은 주석을 참고 바랍니다.)

'-' 연산자를 만난 경우에는, bool check의 값을 true로 설정해준다.

 

 

주석이 없는 코드는 왼쪽 아래 더보기를 참고 바랍니다.

<주석 없는 코드>

#include <iostream>
#include <string>
using namespace std;

int main() {
	string ex;                  
	bool check = false;          
	string number = "";          
	int min_answer = 0;          

	cin >> ex;

	for (int i = 0; i <= ex.size(); i++) {
		if (ex[i] == '-' || ex[i] == '+' || i == ex.size()) {  

			if (check == true) {    
				min_answer -= stoi(number);    
				number = "";                    
			}

			else if (check == false) {
				min_answer += stoi(number);
				number = "";
			}
		}


		else {
			number += ex[i];    
		}

		if (ex[i] == '-') {     
			check = true;
		}
	}

	cout << min_answer;

	return 0;
}

 

 

---

2022년 첫 포스팅이자 오랜만에 쓰는 포스팅이네요..😅

개강하기 전까지는 앞으로 꾸준히 올리도록 노력해야지💪