白俊1463号。

1として作成

質問する

整数Xに使用できる演算は3種類あります.
Xを3で割って、3で割った.
Xを2で割り、2で割ります.
1を減算します.
整数Nが与えられると、上記3つの演算を適宜用いて1が作成される.使用演算回数の最大値を出力してください.

入力

第1の行は、1以上、106以下の整数Nを与える.

しゅつりょく

1行目の演算回数の最大値を出力します.

例

コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	public static Integer arr[];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		arr = new Integer[N+1];
		arr[0] = arr[1] = 0;
		
		System.out.println(func(N));
	}
	
	public static int func(int N) {
		if(arr[N] == null) {
			if(N % 6 == 0)
				arr[N] = Math.min(func(N - 1), Math.min(func(N / 3), func(N / 2))) + 1;
			else if(N % 3 == 0)
				arr[N] = Math.min(func(N / 3), func(N - 1)) + 1;
			else if(N % 2 == 0)
				arr[N] = Math.min(func(N / 2), func(N - 1)) + 1;
			else
				arr[N] = func(N - 1) + 1;
		}
		return arr[N];
	}
}

に答える

3を2で割り、1を1で割ります.いずれの場合も、入力値が1になるように最小値を求める必要があります.
問題解決の過程で生じた錯覚は,単純な高数優先であり,これは最高価格ではないということである.
小数で優先配分しても最高値になります.
各セクションで再帰呼び出しを行う場合は、配列を最高値に更新する必要があります.
ここでは、アレイをIntegerアレイとして宣言します.
IntegerはintのRapperクラスで,基本型をオブジェクトとして扱うクラスである.
資料型ではnullで初期化できません.逆にRAPPERクラスはnull処理が可能であり,展開しない算術演算はできない.
6点を落とした場合は、1点を除いた場合に再帰し、3点の場合に再帰し、2点の場合には再帰で求めた最高値+1でよい.