글 읽기 - { ( [ ] } ) 은 문제 조건에 맞지않은 괄호 인가요?

dydsj0920 6년 전 0

제목 그대로 입니다. { ( [ ] } ) 은 문제 조건에 맞지 않은 괄호 인가요?

그리고 20번 줄처럼 i >j 일때는 왜 return 값을 0이 아닌 1로 해줘야 하나요?

32번 줄의 점화식의 곱하기 특성 때문이라고 생각해야하나요?

//올바른 괄호 문자열
#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstring>


using namespace std;

const long long mod = 1000000;
string s;
string open = "({[";
string close = ")}]";
long long d[101][101];

bool over = false;

long long go(int i, int j) {
	//왜 여기서 return 1을 하는지?
	if (i > j) {
		return 1;
	}
	if (d[i][j] != -1) {
		return d[i][j];
	}
	d[i][j] = 0;
	//왜 k를 두칸씩 뛰어도 되는지?
	for (int k = i + 1; k <= j; k += 2) {
		for (int l = 0; l < 3; l++) {
			if (s[i] == open[l] || s[i] == '?') {
				if (s[k] == close[l] || s[k] == '?') {
					long long temp = go(i + 1, k - 1) * go(k + 1, j);
					if (d[i][j] + temp > mod) {
						over = true;
					}
					d[i][j] += temp;
					d[i][j] %= mod;
				}
			}
		}
	}
	return d[i][j];
}

int main()
{
	int n;
	scanf("%d", &n);
	cin >> s;

	memset(d, -1, sizeof(d));
	long long ans = go(0, n - 1);
	if (over) {
		printf("%05lld\n", ans);
	}
	else {
		printf("%lld\n", ans);
	}
	return 0;
}

kdk8361 6년 전 1

1. 빈 문자열은 올바른 괄호 문자열 -> 올바른 괄호 문자열을 좌우로 같은 계열의 괄호 문자열로 감싸면 올바른 괄호 문자열

{ ( [ ] } )

는 위 방식으로 만들어 질 수 없습니다.

2. 19번 줄에서 1을 리턴하는 이유는 go(i+1, k-1)이 "[]" or "()" or "{}"인 경우를 위해서입니다. 저런 경우 i와 k의 대소관계가 역전이 되겠죠.

3. k를 두칸씩 뛰어도 되는 이유는 올바른 괄호 문자열의 경우 닫는 괄호는 여는 괄호의 홀수번째 뒤에 올 수 밖에 없기 때문입니다.

dydsj0920 6년 전 0

아아 그렇겠군요 감사합니다 도움되었습니다!

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

문제

문제

출처

ICPC

{ ( [ ] } ) 은 문제 조건에 맞지않은 괄호 인가요?

dydsj0920 6년 전 0

kdk8361 6년 전 1

dydsj0920 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말