글 읽기 - 11444번 피보나치 수 6 과 이 문제에서 다른 점이 무엇인가요?

seastar105 5년 전 0

이 문제 피보나치 수 7에서 입력에 0이 추가된 것하고 입력 범위가 줄어든 것과 메모리 제한이 달라진 점 외에는 눈에 띄는 변경점이 없어보여서

피보나치 6을 통과한 코드면 7에서도 잘 되야 할 거 같은데 테스트 케이스 32개만 맞다고 나왔습니다. 어떤 점을 더 고려해야하는 건가요?

아래는 두 문제에 제출했던 코드이고, 행렬 곱셈으로 풀었습니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define MOD 1000000007

using namespace std;

// a = a*b
void mult(long long a[][2], long long b[][2]) {
	long long tmp[2][2];
	tmp[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
	tmp[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
	tmp[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
	tmp[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			a[i][j] = tmp[i][j] % MOD;
}

int main() {
	long long n;
	long long pow[2][2] = { {1,1},{1,0} };
	long long ans[2][2] = { {1,0},{0,1} };
	scanf("%lld", &n);
	if (n <= 1) {
		printf("%lld\n", n);
		return 0;
	}
	else {
		while (n > 0) {
			if (n % 2) {
				mult(ans, pow);
			}
			mult(pow, pow);
			n /= 2;
		}
	}
	printf("%lld\n",ans[0][1]);
	return 0;
}

jh05013 5년 전 0

이걸 그대로 제출하면 201개 다 맞습니다. 반드시 제출했던 코드를 그대로 올려 주세요.

seastar105 5년 전 0

죄송합니다 제가 착각을 했습니다

답변 감사합니다. 질문전에 한번 더 확인하도록 해야겠네요

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

문제

문제

출처

ICPC

11444번 피보나치 수 6 과 이 문제에서 다른 점이 무엇인가요?

seastar105 5년 전 0

jh05013 5년 전 0

seastar105 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말