글 읽기 - 도가뉴 이용했지만 실패..

cks1091 2년 전 0

여기 나와있는 반례들 전부 다 해본것 같은데 어디가 잘못된 건가요??

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

map<long long, long long> memo;

long long MOD = 1000000007;


long long doganu(long long  n){
	
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        memo[1]=1;
		return 1;
    } else if (n == 2) {
		memo[2]=1;
        return 1;
    } else if (memo.count(n) > 0) {
        return memo[n];
    }
	else{
	if(n % 2 == 0){
		long long a = doganu(n / 2 - 1);
		long long b = doganu(n / 2);

		memo[n] = (2 * a + b)% MOD * b % MOD;
		return memo[n];
	}
	else{
		
		long long a = doganu(n / 2 + 1);
		long long b = doganu(n / 2);
		memo[n] = (a * a) % MOD + (b * b) % MOD;
		
		return memo[n];
	}
		
	}
	
}

int main() {
	
	long long n;
	cin>>n;
	cout<<doganu(n);
	
	return 0;

}

circlezer0 2년 전 1

출력할 때 MOD로 한번 더 나머지 연산을 수행해주세요

cks1091 2년 전 0

감사합니다!! mod로 한번씩 나누어서 안해도 될줄알았는데 더해지면서 더 커지는 케이스 가 있는걸 인지 못한거 같습니다!

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

문제

문제

출처

ICPC

도가뉴 이용했지만 실패..

cks1091 2년 전 0

circlezer0 2년 전 1

cks1091 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말