Submission #148406

---

Source Code Expand

import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		new Main().run();
	}

	void run()
	{
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		if(n > 100000) return; //TLE回避
		fibdp = new int[100]; //適当に大きい数
		dp = new int[n+1]; //nより大きい数
		System.out.println(dfs(n));
	}

	int[] fibdp; //フィボナッチ数をメモするための配列
	int getFib(int k){
		//初期値は1, 2からとする
		if(k==0) return 1;
		if(k==1) return 2;
		//すでに探索済みであれば、メモした値を返す
		if(fibdp[k] != 0) return fibdp[k];
		return fibdp[k] = getFib(k-1) + getFib(k-2);
	}

	int[] dp;
	int dfs(int k){
		if(k==0) return 0;
		if(dp[k] != 0) return dp[k];
		int ret = 999999; //適当に大きい数を入れておく
		for(int i=0; i<fibdp.length;i++){
			//もし、i番目のフィボナッチ数が、目的の数を超えていたらbreak
			if(k < getFib(i)) break;
			//k-(i番目のフィボナッチ数)に対して探索を行う
			ret = Math.min(ret, dfs(k - getFib(i)) + 1);
		}
		return dp[k] = ret;
	}
}

Submission Info

Judge Result