백준 1541 잃어버린 괄호

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

 

서론

쉬운문제였는데 혼자 풀어내지 못했다.

풀이를 볼 때 조금 더 생각하지 않았음에 오는 아쉬운 문제가 있고 보길 잘했다는 생각이 드는 문제가 있다.

풀이를 빠르게 볼지 말지를 선택하는것은 어려운 일이다.

 

아이디어

그리디 알고리즘 문제라서 규칙성이 있을거라는 생각은 했지만 찾지 못했다.

모든 경우의 수를 일단 계산해볼까 생각했으나 이것도 쉬운일은 아니었다.

 

간단하게 '-'가 나올때까지 입력값을 tokenization 해주면 된다.

입력값이 55-50+40 이면 괄호를 50-(50+40) 해주면 되고

100-20-10이면 100-(20)-(10)

100-30+20-40+10이면 100-(30+20)-(40+10)이다.

직관적으로 음수에서 괄호를 만들어주면 최저값이 나오는것을 볼 수 있다.

괄호는 strtok를 이용하여 음수에서 입력값을 자르면 된다.

 

구현

//c++
#pragma warning (disable : 4996)

#include <iostream>
#include <cstring>

using namespace std;

char s1[51];
char s2[51][51];

int tok1st() {
	cin >> s1;
	int idx = 0;
	char *tok = strtok(s1, "-");
	while (tok != NULL) {
		strcpy(s2[idx], tok);
		tok = strtok(NULL, "-");
		idx++;
	}
	return idx;
}

int tok2nd(int idx) {
	int result = 0;
	for (int i = 0; i < idx; i++) {
		int sum = 0;
		char *tok = strtok(s2[i], "+");
		while (tok != NULL) {
			sum += atoi(tok);
			tok = strtok(NULL, "+");
		}
		if (i == 0) result += sum;
		else result -= sum;
	}
	return result;
}

int main() {
	cout << tok2nd(tok1st());
}