글 읽기 - 반례 좀 찾아주세요.ㅜㅜ

karcho 3년 전 0

저랑 비슷하게 문제를 푼 사람이 없더라구요 ㅠㅠ

테스트벤치 나와있는거 거의 다 실행해 봤는데 값이 계속 맞게 나와서

뭐가 틀렸는지 모르겠어요 ㅠㅠ

46%에서 틀렸습니다가 나오는데 혹시 이 부분에서 해결하신분 있으면 알려주세요 ㅠㅠ

- 대략적인 알고리즘-

1. ()와 []가 나오는 경우가 있으면 따로 분리해서 문제를 풀었어요.

2. 배열을 이용해서 더하기 연산이 이렇게 작동되게 코드를 짰어요.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

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

	stack<char> stack;
	string s;
	getline(cin, s);
	int size = 0 , fail = 0, count = 0;
	int a[100] = { 0 };
	for (int i = 0; i < s.length(); i++) {
		if (stack.empty()) {
			int idx = 0;
			for (int i = 0; i < 100; i++) {
				if (a[i] == 0) {
					idx = i;
					break;
				}
			}
			size = idx;
		}

		if (s[i] == '('&&s[i + 1] == ')') {
			a[size] += 2;
			i++;
		}
		else if (s[i] == '['&&s[i + 1] == ']') {
			a[size] += 3;
			i++;
		}
		else if (s[i] == '(' || s[i] == '[') {
			stack.push(s[i]);
			size++;
		}
		else if (s[i] == ')') {
			if (!stack.empty()) {
				if (stack.top() == '(') {
					a[size] *= 2;
					a[size - 1] += a[size];
					a[size] = 0;
					size--;					
					stack.pop();
				}
				else fail = 1;
			}
			else fail = 1;
		}
		else if (s[i] == ']') {
			if (!stack.empty()) {
				if (stack.top() == '[') {
					a[size] *= 3;
					a[size - 1] += a[size];
					a[size] = 0;
					size--;					
					stack.pop();
				}
				else fail = 1;
			}
			else fail = 1;
		}	
		
	}
	for (int i = 0; i < 100; i++) {
		count += a[i];
	}
	if (!fail)
		cout << count;
	else cout << "0" ;

}

karcho 3년 전 1

반례는 ()[ 였고, 마지막 if문에

if(!fail) 를 if(!fail&&stack.empty())로 바꾸면 해결됩니다.

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

문제

문제

출처

ICPC

반례 좀 찾아주세요.ㅜㅜ

karcho 3년 전 0

karcho 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말