글 읽기 - 반례에 대한 조언 부탁드립니다.

sgchoi5 5년 전 0

안녕하세요.

질문 게시판 공지사항 확인 및 지난 질문 확인하였습니다.

스택 말고 "재귀"로 한 번 풀어보려고 했는데, 잘 안 되네요.

시작하자마자 틀렸습니다가 나오는 것을 보니 뭔가 기본적인 것을 고려하지 못한 상황인 듯 합니다.

동작 방식은

main 에서 xxx(...) 단위로 잘라서 getLen() 으로 던지면 중첩인 경우에 ...) 만 잘라서 재귀호출하게 됩니다.

TC 를 만들어보면서 이런 저런 상황을 고려하다보니 재귀 호출시의 예외처리만 늘어나고 있네요.

#include <cstdio>
char com[51];
char t[51];

int getLen(char* str) {
	bool left = false;
	int out_len = 0;
	int in_len = 0;
	int mul = 0;

	for (int i = 0; str[i]; i++) {
		if (str[i] == '(') {
			left = true;
			break;
		}
		else if (str[i] == ')') {
			left = false;
			break;
		}
	}

	for (int i = 0; str[i]; i++) {
		if (str[i + 1] == '(') {
			mul = str[i] - '0';
			in_len += getLen(&str[i + 2]);
			in_len *= mul;

			int l = 0, r = 0;
			int additional = 0;
			for (int k = i + 1; str[k]; k++) {
				if (str[k] == '(')
					l++;
				if (str[k] == ')')
					r++;
				if (l == r) {
					for (int m = k + 1; str[m]; m++) {
						if (str[k] != '(' && str[m] != ')')
							additional++;
						else
							break;
					}
					break;
				}
			}
			return in_len + out_len + additional;
		}
		else if (str[i] == ')') {
			return in_len;
		}
		else {
			if (left)
				out_len++;
			else
				in_len++;
		}
	}
	return in_len + out_len;
}

int strlen(char* p) {
	int cnt = 0;
	while (*p++ != '\0') {
		cnt++;
	}
	return cnt;
}

int main(void) {
	int ans = 0;
	scanf("%s", com);

	int totlen = strlen(com);

	int l = 0;
	int r = 0;
	for (int i = 0, ti = 0; com[i]; i++) {
		if (com[i] == '(')
			l++;
		if (com[i] == ')')
			r++;

		t[ti++] = com[i];
		if (l > 0 && l == r) {
			l = 0;
			r = 0;
			t[ti] = '\0';
			ti = 0;
			totlen -= strlen(t);
			ans += getLen(t);
		}
	}

	printf("%d\n", ans + totlen);
	return 0;
}

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

문제

문제

출처

ICPC

반례에 대한 조언 부탁드립니다.

sgchoi5 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말