글 읽기 - 5095번 어느 부분이 틀린지 잘 모르겠습니다.

(追記) (追記ここまで)

5095번 어느 부분이 틀린지 잘 모르겠습니다.

5095번 - Matrix Powers

thdtjdals3 4년 전 0

오버플로우 문제인가 싶어서, 굳이 Matrix 안의 배열을 long long으로 늘려보기도 했는데 여전히 틀렸습니다만 뜨네요.

50%에서 틀리므로 뭔가 반례가 있을 것 같은데, 게시판에 딱히 반례는 없고 구글에 NZPC 2011을 검색해봐도 답안이 뜨질 않아서요.

다른 문제들, 특히 10830번 행렬 제곱과 거의 같은 문제라고 판단해서, 10830번에 제출했던 코드를 그대로 가져와보기도 했는데 실패하네요.

(예제는 통과했습니다.)

10830번에서는 1120KB, 0ms로 통과했는데...

어떻게 하면 좋을까요?

/*10830번 제출 코드
#include <stdio.h>
typedef struct {
	long long array[5][5];
} Matrix;
Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M);
Matrix matrix_power_modular (Matrix A, long long K, int N, long long M);
int main() {
	
	int N;
	long long B;
	scanf("%d %lld", &N, &B);
	
	Matrix Base;
	
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &Base.array[i][j]);
		}
	}
	
	Base = matrix_power_modular (Base, B, N, 1000);
	
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%d ", Base.array[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < N; k++) {
				int temp = A.array[i][k] * B.array[k][j];
				result.array[i][j] += temp % M;
			}
			result.array[i][j] %= M;
		}
	}
	return result;
}
Matrix matrix_power_modular (Matrix A, long long K, int N, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i == j) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular (result, A, N, M);
		}
		A = matrix_multiply_modular (A, A, N, M);
		K >>= 1;
	}
	return result;
}
*/
5095번에 제출한 코드
#include <stdio.h>
typedef struct {
	long long array[100][100];
} Matrix;
Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M);
Matrix matrix_power_modular (Matrix A, int K, int N, long long M);
int main() {
	
	int N, M, P;
	scanf("%d %d %d", &N, &M, &P);
	
	Matrix Base;
	
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%lld", &Base.array[i][j]);
		}
	}
	
	int zero1, zero2, zero3;
	scanf("%d %d %d", &zero1, &zero2, &zero3);
	
	Base = matrix_power_modular (Base, P, N, M);
	
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%lld ", Base.array[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < N; k++) {
				int temp = A.array[i][k] * B.array[k][j];
				result.array[i][j] += temp % M;
			}
			result.array[i][j] %= M;
		}
	}
	return result;
}
Matrix matrix_power_modular (Matrix A, int K, int N, long long M) {
	Matrix result;
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i == j) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular (result, A, N, M);
		}
		A = matrix_multiply_modular (A, A, N, M);
		K >>= 1;
	}
	return result;
}

kyo20111 4년 전 2

zero를 그냥 입력받는게 아니라 n, m, k가 모두 0일때까지 입력을 받는것입니다.

int main(){
 while(1){
 scanf("%d %d %d",&n,&m,&p);
 if(n == 0 && m == 0 && p == 0) break;
 // 연산하기
 }
}

thdtjdals3 4년 전 0

정말 감사합니다... 케이스 하나당 한 문제?씩만 있는 줄 알았네요 ᅮᅮ

kyo20111 4년 전 4

그리고 고통받고 있으신듯 하니 추가로 하나 더 알려드리자면 출력형식을 잘 보면 예제가 2번 입력된다 했을 때 다음과 같이 출력해야합니다.

thdtjdals3 4년 전 0

죄송하지만 하나만 더 질문 드려도 될까요?

출력 형식이 잘못되었다고 하여 행렬을 출력할 때 각 열 맨 끝의 스페이스바가 문제가 되는 걸까 해서, 소스코드처럼 출력문을 짜보았습니다.

그런데도 출력 형식 에러가 안 고쳐져서 뭔가 제가 놓친 점이 있는지 의문인데... 정말 죄송하지만 도와주실 수 있을까요??

printf("\n");
for (i = 0; i < N; i++) {
	for (j = 0; j < N; j++) {
		printf("%lld", Base.array[i][j]);
		if (j < N - 1) {
			printf(" ");
		}
	}
	printf("\n");
}

thdtjdals3 4년 전 0

아 이미 댓글 올려주셨었군요 감사합니다!!

thdtjdals3 4년 전 1

kyo20111님 정말 감사합니다 출력 예시 안 올려주셨으면 평생 모를 뻔 했어요...!

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

5095번 어느 부분이 틀린지 잘 모르겠습니다.

thdtjdals3 4년 전 0

kyo20111 4년 전 2

thdtjdals3 4년 전 0

kyo20111 4년 전 4

thdtjdals3 4년 전 0

thdtjdals3 4년 전 0

thdtjdals3 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말