글 읽기 - 도움을 청합니다. 반례를 찾지 못하겠습니다.

gyuhwan 4년 전 0

A라는 2차원 배열에 이미지 데이터를 저장한 후,

네 구역으로 나누어 순차적으로 재귀 호출을 수행하는 divide 함수를 호출해,

기저 사례 n == 1 일때 char 벡터인 res의 back에 해당 좌표의 요소를 추가시키며,

기저 사례의 함수를 호출했던 함수 스택에서 최근에 res의 back에 추가된 요소들 4개에 대하여 요소의 값이 같다면

optimize를 수행하는 방식으로 구현했습니다.

제출 후에 WA를 받아서, 제가 생각한 예외 케이스와 다른 질문에 있는 테스트 케이스를 넣어도,

정답이 잘 나오는 상황이라서 혼자 해결하기에는 버거운 것 같아, 조심스럽게 도움을 청합니다.

#include <cstdio>
#include <vector>

using namespace std;

char A[70][70];
vector<char> res;

void optimize(int to) {
	for (int i = 0; i < 5; i++) {
		res.pop_back();
	}
	
	res.push_back(to);
} 

void divide(int x, int y, int n) {
	if (n == 1) {
		res.push_back(A[x][y]);
		return;
	}
	
	res.push_back('(');
	
	int midx = x + n / 2;
	int midy = y + n / 2;

	divide(x, y, n / 2); 
	divide(midx, y, n / 2);
	divide(x, midy, n / 2);
	divide(midx, midy, n / 2);
	
	int len = res.size();
	
	char last = res[len - 1];
	for (int i = 2; i <= 4; i++) {
		char item = res[len - i];
		if (last != item) {
			res.push_back(')');
			return;
		}
		
		last = item;
	}
	
	optimize(last);
}

int main(void) {
	int N; scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf(" %c", &A[j][i]);
		}
	}
	
	divide(1, 1, N);
	
	for (char x : res) {
		printf("%c", x);
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

도움을 청합니다. 반례를 찾지 못하겠습니다.

gyuhwan 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말