白駿1463草

リンクテキスト
初めて問題を見るときは、1、2、3を演算するif文を簡単に運用し、入力した数が1になるまで繰り返して解くだけです.
もちろん間違っています.

	while (x != 1) {
		if (x % 3 == 1) {
			x = x - 1;
			answer++;
			continue;
		}
		if (x % 3 == 2) {
			x = x - 1;
			answer++;
			continue;
		}
		//1번 연산 검사
		if (x % 3 == 0) {
			x = x / 3;
			answer++;
			continue;
		}
		if (x % 2 == 0) {
			x = x / 2;
			answer++;
			continue;
		}
		if (x % 3 != 0 && x % 2 != 0) {
			x = x - 1;
			answer++;
			continue;
		}
    }

何かよく知っている方法で間違いがあった...
前回も似たような方法でこのような問題を解決したが、結果は答えが得られず、コードもめちゃくちゃになり、削除して、再び解いたことがある.
そんな経験に基づいて、今度はすぐに考え直した.
入力した数字は1から徐々に増加し、ルールを見つけようとし、20まで書くとルールが見つかりました.
まず、問題を解く方法はダイナミックプログラミングを採用すべきだと気づきました.
2の倍数または3の倍数でない場合、インデックスの値は以前のインデックスの値に1を加算するルールが見つかりました.(dp[i] = dp[i-1]+1)
現在2の倍数である場合、または3の倍数である場合、3で割ると前の3の倍数でもう一度演算することになり、dp[i]=dp[i/3]+1に等しい.2の倍数も同じです.
そう思ってコードを提出しましたが、また間違っていました・・・
反例があるかどうか知りたくて、掲示板をしばらくぶらぶらしてから知りました.すなわち、1つのdp[i/3]+1の値は、dp[i−1]+1よりも大きい場合がある.
これに基づいてコードを再修正した結果、正解が見つかりました.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int dp[1000001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	int x;
	cin >> x;

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	dp[6] = 2;

	for (int i = 7; i <= x; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 3 == 0) {
			dp[i] = min(dp[i / 3]+1, dp[i]);
		}
		if (i % 2 == 0) {
			dp[i] = min(dp[i / 2]+1, dp[i]);
		}
	}
	cout << dp[x] << '\n';
	return 0;
}