글 읽기 - 맞긴 맞았으나, 반례를 못 찾겠습니다.

park780172 4년 전 0

우선 첨부한 코드는 정답 코드입니다.

저의 구현 방식은

( 또는 { 또는 [ 나올 때만,
그 괄호에 해당하는 점수를 sum에 누적하여 더합니다.

) 또는 } 또는 ] 나올 때에는
그 괄호에 해당하는 점수를 sum에서 뺍니다.

위의 과정 중 나오는 sum의 최댓값(=Max)이 정답이라고 생각하였습니다.

26번 째 줄의

else를 지우면, 정답이 틀리다고 나오고,

어차피 순간 순간의 누적된 sum의 최댓값(=Max)이 정답이라고 생각하는데,

이에 대한 반례를 못 찾겠습니다.

제가 어느 부분을 놓치고 있을까요??

#include <bits/stdc++.h>

using namespace std;

int sum, Max;

int main(void)
{
	string s;
	getline(cin, s);

	for (auto i : s)
	{
		if (i == '(' || i == '{' || i == '[')
		{
			if (i == '(') sum += 1;
			else if (i == '{') sum += 2;
			else if (i == '[') sum += 3;
		}
		else if (i == ')' || i == '}' || i == ']')
		{
			if (i == ')') sum -= 1;
			else if (i == '}') sum -= 2;
			else if (i == ']') sum -= 3;
		}
		else Max = max(Max, sum);		
	}

	printf("%d\n", Max);

	return 0;
}

sait2000 4년 전 1

(1()) 이런 게 있으면 어떡해요?

park780172 4년 전 0

@sait2000

아 제가 문제 지문을 아예 잘못 보고, 잘못 해석했습니다.

문자열 S는 올바른 괄호 문자열에 숫자를 끼워 넣은 형태라고 나와 있어서,

()와 같은 문자열을 입력되지 않는다라고 생각하였습니다.

빈 문자열은 공백(띄어쓰기)으로 생각하여, getline으로 받았네요.

어쩐지 입력 조건에 빈 문자열이 아니고, 숫자를 포함하고 있다고 해서

()는 아예 생각 안 했고,

입력 문자열이 빈 문자열이 아닌데 왜 1번과 같은 조건이 주어졌는지 잠깐 생각했다가 그냥 무시했었네요.

댓글 감사합니다.

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

문제

문제

출처

ICPC

맞긴 맞았으나, 반례를 못 찾겠습니다.

park780172 4년 전 0

sait2000 4년 전 1

park780172 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말