[Algorithm]純白準14631を使用

9464 ワード
白駿 どうてきけいかくほう テキストリンク

0、問題


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

1.アイデア


演算順序:-1、/3、/2

2.コア解答


演算順序:-1、/3、/2
for(int i=2; i<=n; i++) {
			dp[i] = dp[i-1]+1;
			if(i%2 == 0) dp[i] = Math.min(dp[i], dp[i/2]+1);
			if(i%3 == 0) dp[i] = Math.min(dp[i], dp[i/3]+1);
}

3.コード

import java.io.*;
public class DP_11 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int dp[] = new int[n+1];
		dp[0] = dp[1] = 0;
		
		for(int i=2; i<=n; i++) {
			dp[i] = dp[i-1]+1;
			if(i%2 == 0) dp[i] = Math.min(dp[i], dp[i/2]+1);
			if(i%3 == 0) dp[i] = Math.min(dp[i], dp[i/3]+1);
		}
		
		System.out.println(dp[n]);
	}
}

4.結果



成功～
Algorithm & Data Structure - Linked List(3/Doubly Linked List)
Data Parallel Computing