글 읽기 - 데이터 추가

yclock 7년 전 0

@mino 님의 소스 코드를 보면, O(N^2 * 200^2)으로 풀었음에도 불구하고, 1.5s 내에 결과가 나왔습니다.

고로 다음 데이터를 추가해 주시면 정말 감사하겠습니다.

아래에 첨부된 소스를 실행시키면, 표준출력으로 입력 데이터를 출력합니다.

시간초과를 내는 방식이, DFS를 돌 때, 방문하는 방향의 순서에 굉장히 의존적입니다.

이는, 첨부된 소스에서 2차원 배열 A를 출력할 때, 출력하는 순서에 변화를 주면 해결할 수 있습니다.

ex) for(int i = 1; i <= N; i++) -> for(int i = N; i; i--)

참고로 정확한 답은 100입니다.

// yclock's Data Hack!
#include <stdio.h>

const int N = 100;
const int Mn = 0;
const int Mx = 200;
int A[N+5][N+5];

int main() {
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
		A[i][j] = (Mn+Mx)>>1;
	for(int i = 2; i < N; i++) A[2][i] = Mx;
	for(int i = 2; i <= N; i++) A[i][N-1] = Mx;
	A[N][N] = Mn;

	printf("%d\n", N);
	for(int j = 1; j <= N; j++) {
		for(int i = 1; i < N; i++) printf("%d ", A[i][j]);
		printf("%d", A[N][j]);
		if(N != j) putchar('\n');
	}
	return 0;
}

yclock 7년 전 0

다른 버젼

// yclock's Data Hack 2!
#include <stdio.h>

const int N = 100;
const int Mn = 0;
const int Mx = 200;
int A[N+5][N+5];

int main() {
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
		A[i][j] = (Mn+Mx)>>1;
	A[N-1][N] = A[N][N-1] = Mx; A[N][N] = 0;

	printf("%d\n", N);
	for(int j = 1; j <= N; j++) {
		for(int i = 1; i < N; i++) printf("%d ", A[i][j]);
		printf("%d", A[N][j]);
		if(N != j) putchar('\n');
	}
	return 0;
}