글 읽기 - [16637 괄호 추가하기] C++ permutation 풀이.. 틀렸습니다..

mycool0905 4년 전 0

permutation으로 완전탐색하여 풀이 했는데, 40%에서 계속 틀렸다고 뜨네요.

테스트 케이스와 질문에 있는 여러가지 반례 넣었는데 다 잘 돌아갑니다.

음수끼리의 곱도 다 고려했는데, 어느 부분에서 틀렸는지 모르겠습니다.

주석도 자세히 달아놨습니다.

고수분들 조언 부탁드립니다..ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int answer;

int calculate(int a, char op, int b) {
	switch (op) {
	case '+': return a + b;
	case '-': return a - b;
	case '*': return a * b;
	}
}

void operate(vector<char> equation, int N, int opCount, int maxCount) {
	vector<int> temp;
	vector<char> tempEquation;
	int tempAnswer;
	bool flag;

	for (int i = maxCount; i < opCount; i++)
		temp.push_back(0);
	for (int i = 0; i < maxCount; i++)
		temp.push_back(1);

	/* 중첩된 괄호는 없고 각 연산자 하나와 양쪽 피연산자 하나씩 묶이기 때문에 */
	/* 바로 옆 연산자에는 괄호를 못 넣음 */
	do {
		flag = true;
		for (int i = 0; i < temp.size(); i++) {
			if (temp[i] == 1) {
				if (i == 0) {
					if (temp[i + 1] == 1) {
						flag = false;
						break;
					}
				}
				else if (i == temp.size() - 1) {
					if (temp[i - 1] == 1) {
						flag = false;
						break;
					}
				}
				else {
					if (temp[i - 1] == 1 || temp[i + 1] == 1) {
						flag = false;
						break;
					}
				}
			}
		}

		if (!flag)
			continue;

		/* 중첩된 괄호가 없으면 괄호 연산 먼저 실행 */

		tempEquation = equation;
		
		for (int i = 0; i < temp.size(); i++) {
			if (temp[i] == 1) {
				tempEquation[2 * i] = calculate(tempEquation[2 * i] - 48, tempEquation[2 * i + 1], tempEquation[2 * i + 2] - 48) + 48;
				tempEquation[2 * i + 1] = '!';
				tempEquation[2 * i + 2] = '!';
			}
		}

		/* 괄호 연산을 실행한 곳은 !로 바꾸어 놓고 안된 부분만 실행하기 */
		tempAnswer = tempEquation[0] - 48;
		for (int i = 1; i < N; i = i + 2) {
			if (tempEquation[i] == '!')
				continue;
			tempAnswer = calculate(tempAnswer, tempEquation[i], tempEquation[i + 1] - 48);
		}
		answer = max(answer, tempAnswer);
	} while (next_permutation(temp.begin(), temp.end()));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	char input;
	vector<char> equation;
	
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> input;
		equation.push_back(input);
	}

	/* 괄호를 하나도 안 넣었을 때 값 구해놓기 */
	answer = equation[0] - 48;
	for (int i = 1; i < N; i = i + 2) {
		answer = calculate(answer, equation[i], equation[i + 1] - 48);
	}

	if (N == 1 || N == 3) {
		cout << answer << "\n";
		return 0;
	}

	/* op가 1개 일 때, 괄호의 최대 개수 1 */
	/* op가 2개 일 때, 괄호의 최대 개수 1 */
	/* op가 3개 일 때, 괄호의 최대 개수 2 */
	/* op가 4개 일 때, 괄호의 최대 개수 2 */
	/* ... */
	/* op가 m개 일 때, 괄호의 최대 개수 int((float)m/2+0.5) */
	
	int maxCount = int((float)(N / 2) / 2 + 0.5);

	for (int i = 1; i <= maxCount; i++) {
		operate(equation, N, N / 2, i);
	}

	cout << answer << "\n";

	return 0;
}

park780172 4년 전 1

11
9*9*9*9*9*9

correct : 531441
wrong : 2480625

mycool0905 4년 전 0

@park780172

와.. 반례 감사합니다.

int <-> char 타입 캐스팅을 잘못해서 값이 잘못 나왔네요.

감사합니다.

mycool0905 4년 전 0

@park780172

또한 찾아본 결과 아스키코드가 127까지 존재해서 127이 넘으면 안되는 것 같네요.

9*9 = 81이고, 48을 더하니 129가 되어서 이상한 값으로 바뀌는 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[16637 괄호 추가하기] C++ permutation 풀이.. 틀렸습니다..

mycool0905 4년 전 0

park780172 4년 전 1

mycool0905 4년 전 0

mycool0905 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말