글 읽기 - 반례를 못찾겠습니다.. 로직은 맞는거 같은데 80%대에서 틀립니다.

ojh4110 5년 전 0

문제의 테스트케이스와 제가 만들어본 케이스는 전부 잘 돌아갑니다.

로직에서 아무리 생각해도 어디서 틀렸는지 모르겠어서 질문드립니다.

혹시 로직에서 틀린점이나 반례 알려주시면 정말 감사하겠습니다...

소스코드에 간단한 설명 주석으로 달아놨습니다!

#include <vector>
#include <iostream>
#include <queue>

using namespace std;
long long nums[15];
char oper[15];

// first 가 1이면 index와 index+1에 괄호가 쳐져 있는것.
int first[15];
// first가 (1,2) (2,3) 이 불가능 하므로 어떤 수가 괄호로 묶여있는지 표시해줌
int visit[15];

// 이미 그 연산자가 사용이 됬는지 표시
bool operEnd[15];

// 숫자 개수와 연산자 개수
int numNum;
int operNum;


long long operation(char oper, long long first, long long second){
	switch (oper)
	{
	case '+':
		return first + second;
	case '-':
		return first - second;
	case '*':
		return first * second;
	default:
		return 0;
		break;
	}
}




long long calc(){
	long long temp[15];
	for (int i = 0; i < numNum; i++)
	{
		temp[i] = nums[i];
		operEnd[i] = 0;
	}
    // 처음에 괄호로 묶인 수들을 전부계산해 주고 결과를 temp 배열에 넣어줌
    // i와 i+1에 둘다 넣어준 이유는 아래 포문에서 연산자를 기준으로 앞에있을지 뒤에 있을지 몰라 넣어줌
	for (int i = 0; i < numNum; i++)
	{
		if (first[i] == 1){
			long long result = operation(oper[i], temp[i], temp[i + 1]);
			operEnd[i] = true;
			temp[i] = result;
			temp[i + 1] = result;
		}
	}

    
    // 두번째 for문에서 아직 계산되지 않은 연산자들을 계산해줌
    
	long long result = 0;
	bool isFirst = true;
	for (int i = 0; i < operNum; i++)
	{
		if (!operEnd[i]){
			if (isFirst){
				result += operation(oper[i], temp[i], temp[i + 1]);
				isFirst = false;
			}
			else{
				result = operation(oper[i], result, temp[i + 1]);
			}
		}
	}
	return result;
}

long long ans;

//괄호를 선택해줌
void dfs(int index){
	if (index == numNum - 1){
		ans = max(calc(), ans);
		return;
	}

	if (visit[index] == 0){

		visit[index] = 1;
		visit[index + 1] = 1;
		first[index] = 1;

		dfs(index + 1);

		visit[index] = 0;
		visit[index + 1] = 0;
		first[index] = 0;
	}

	dfs(index + 1);

}


int main() {
	//freopen("input.txt", "r", stdin);
	int total;
	ans = -5000000000LL;
	cin >> total;
	numNum = 0;
	operNum = 0;

	if (total == 1){
		int result;
		cin >> result;
		cout << result;
	}
	else{
		for (int i = 0; i < total; i++)
		{
			if (i % 2 == 0){
				cin >> nums[numNum++];
			}
			else{
				cin >> oper[operNum++];
			}
		}

		dfs(0);

		cout << ans;

	}

	return 0;
}

thdms5128 4년 전 1

N이 1인 경우를 처리안하셔서 그럴꺼에요!

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.. 로직은 맞는거 같은데 80%대에서 틀립니다.

ojh4110 5년 전 0

thdms5128 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말