글 읽기 - 제 나름 틀린부분이 없다고 생각드는데 중간에 틀리네요.. 그리고 속도 질문!!

muscj7 5년 전 0

페이퍼의 가운데 인덱스로부터 8방+현위치(가운데)를 분할정복을 통해 탐색하면서 -1과 0과 1페이퍼의 개수를 구했습니다.

초기 사이즈가 1일 때, 3일 때, ~27일 일때 까지 다양한 케이스로 해봤지만 예외 케이스를 찾지 못했습니다.

제 알고리즘이 어디에 문제가 있는지 알고 싶습니다.

#include <stdio.h>
#include <vector>
using namespace std;

#define MAX 2188
#define NONE 3 // 검사한 9구역이 모두 같지 않을 때는 사용

int paper[MAX][MAX]; // 1~
int answer[4];

int divide(int start, int end, int sign) {
	// 가장 작은 조각의 페이퍼인가?
	if (sign == 1)
		return paper[start][end];

	sign /= 3;
	vector<int> pp;

	// 9구역 방문
	for (int s_diff = -sign; s_diff < sign + 1; s_diff += sign)
		for (int e_diff = -sign; e_diff < sign + 1; e_diff += sign)
			pp.push_back(divide(start - s_diff, end - e_diff, sign));

	// isSame 구하기 : 9개의 페이퍼가 같은지 구하기
	int isSame = 1, len = pp.size();
	for (int i = 0; i < len - 1; i++) 
		if (pp[i] != pp[i + 1])
			isSame = false;

	// 모두가 같은 페이퍼인가?
	if (isSame)
		return pp[0];

	// 각각 다른 페이퍼인가?
	else 
		for (int i = 0; i < len; i++)
			answer[pp[i] + 1]++; // -1은 index 0에 저장, 0은 1에 저장, 1은 2에 저장
	return NONE;
}

int main()
{
	int max, k;
	scanf("%d", &max);

	// 입력
	for (int r = 1; r <= max; r++) {
		for (int c = 1; c <= max; c++) {
			scanf("%d", &k);
			paper[r][c] = k;
		}
	}

	// 계산
	if (max <= 3)
		answer[divide((1 + max) / 2, (1 + max) / 2, max) + 1]++;
	else
		divide((1 + max) / 2, (1 + max) / 2, max);

	// 출력
	printf("%d\n%d\n%d\n", answer[0], answer[1], answer[2]);
	return 0;
}

djm03178 5년 전 1

56번째 줄을 max <= 3일 때만 수행하는 것이 이상합니다.

9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

muscj7 5년 전 0

djm님 또 감사합니다!.. 흠..생각을해서 한다는게 자꾸 저런 실수를 해버리네요..

muscj7 5년 전 0

***

제출 결과

메모리 속도

19876KB 548MS

와 같은 결과가 나왔습니다. 생각보다 속도가 느린 느낌인데

위 소스에서 속도에 영향을 주는 요인들이 뭐가 있는지 여쭤봐도 될까요??

djm03178 5년 전 1

다른 정답 코드들과 비교했을 때 특별히 느린 편은 아닌 것 같습니다. 이 프로그램에서 압도적으로 속도에 저하를 주는 요인은 입출력입니다. 같은 코드인데 scanf로 입력을 받으면 476MS가 나왔던 것이, fread로 fast I/O를 구현하니 68MS로 줄었습니다.

djm03178 5년 전 1

그 외에 시간이 좀 더 많이 걸리는 요인을 찾자면 매 호출마다 vector 객체가 하나 생성되고 파괴되는 것이 무겁다는 것과, 루프를 최대 3회씩 도는 것 정도를 뽑을 수 있을 것 같습니다.

muscj7 5년 전 0

아.. 그렇군요

fread를 이용하는 방법을 공부해봐야겠어요!

두 번째로 말씀해주신 벡터관련 프로그래밍 방식은 함수 호출이 잦은 알고리즘에서는 더 효율적인 방법을 생각해봐야겠군요 ㅠ ㅎㅎ

늦은 시간 답변주셔서 감사합니다

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

문제

문제

출처

ICPC

제 나름 틀린부분이 없다고 생각드는데 중간에 틀리네요.. 그리고 속도 질문!!

muscj7 5년 전 0

djm03178 5년 전 1

muscj7 5년 전 0

muscj7 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

muscj7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말