#include <stdio.h> int Dp[1000001]; int min(int a, int b) { return a > b ? b : a; } int main(void) { int N; scanf("%d", &N); Dp[1] = 0; for (int i = 2; i <= N; i++) { Dp[i] = Dp[i - 1] + 1; if (i % 2 == 0) Dp[i] = min(Dp[i], Dp[i / 2] + 1); if (i % 3 == 0) Dp[i] = min(Dp[i], Dp[i / 3] + 1); } printf("%d\n", Dp[N]); return 0; } |
디피문제 단순하게 점화식을 만들어서 저장하는 것입니다. 이것을 만들기 위해서는 아래서 부터 계산할 것인지 뒤에서 부터 계산해 나갈 것인지르 결정합니다. 그리고 존재하는 경우의 수에 대해서 처리를 어떻게 하고 민 맥스 값을 언제 넣어줄 것인지를 주의하면 됩니다. 오께이. |