글 읽기 - [틀렸습니다]

ehdgur0114 3년 전 0

안녕하세요. 문제를 풀면서 어려움이 있어서 질문 남깁니다.

해당 코드를 돌리면 '틀렸습니다.'가 출력됩니다. 배열을 이용하여 피보나치수를 구하였고 거듭제곱을 할 때에는 분할 정복을 이용하였습니다. 몇가지 테스트케이스를 돌릴 때에는 정확한 답이 나오는데 무엇이 문제일까요?

#include <stdio.h>

long long int arr[2][2];
long long int temp_arr[2][2];
long long int ans[2][2];

void matmul(int num){
  if(num==1){
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        long long int temp_ans=0;
        for(int k=0;k<2;k++){
          temp_ans+=((arr[i][k]%1000000)*(temp_arr[k][j]%1000000))%1000000;
        }
        ans[i][j]=temp_ans%1000000;
      }
    }
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        temp_arr[i][j]=ans[i][j]%1000000;
      }
    }
  }else if(num==2){
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        long long int temp_ans=0;
        for(int k=0;k<2;k++){
          temp_ans+=((temp_arr[i][k]%1000000)*(temp_arr[k][j]%1000000))%1000000;
        }
        ans[i][j]=temp_ans%1000000;
      }
    }
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
        temp_arr[i][j]=ans[i][j]%1000000;
      }
    }
  }
}

void power(int n){
  if(n==0) return;
  power(n/2);
  matmul(2);
  if(n%2!=0){
    matmul(1);
  }
}

long long int fib(long long int n){
  arr[0][0]=1;
  arr[0][1]=1;
  arr[1][0]=1;
  arr[1][1]=0;
  temp_arr[0][0]=1;
  temp_arr[0][1]=0;
  temp_arr[1][0]=0;
  temp_arr[1][1]=1;
  power(n);
  return ans[1][0]%1000000;
}

int main(void){
  long long int n;
  scanf("%lld",&n);
  printf("%lld",fib(n));
}

sr5757 3년 전 0

매개변수의 자료형을 수정해주시면 됩니다!

ehdgur0114 3년 전 0

헉 그렇네요. 조언 감사합니다..!

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

문제

문제

출처

ICPC

[틀렸습니다]

ehdgur0114 3년 전 0

sr5757 3년 전 0

ehdgur0114 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말