문제
#1463: 해봐 1
첫 번째 행은 1보다 크거나 같고 106보다 작거나 같은 정수 N을 포함합니다.
www.acmicpc.net
규칙을 찾아
항상 동적 프로그래밍(DP) 문제와 마찬가지로 재귀를 찾는 것이 가장 중요합니다.
예제에서 입력 및 출력이 있는 규칙을 살펴보겠습니다.
사용 가능한 작업은 다음과 같습니다.
1. X가 3으로 나누어지면 3으로 나눕니다.
2. X가 2로 나누어지면 2로 나눕니다.
3. 1을 뺍니다.
– 2를 입력한 경우
동작 2를 수행할 수 있으므로 수행한다. 즉시 1이 되므로 총 작업 수는 1입니다.
– 10을 입력한 경우
작업 3을 수행하여 9로 만들고 작업 1을 수행한 다음 다시 작업 3을 수행합니다. 총 작업 횟수는 3회입니다.
– 4를 입력한 경우
동작 3(3) → 동작 1(1), 동작 2(2) → 동작 2(1). 최소 2번의 수술이 필요합니다.
– 5를 입력한 경우
동작 3 → 동작 2 → 동작 2. 최소 3개의 동작이 필요합니다.
또한 5는 2나 3으로 나눌 수 없기 때문에 항상 3번 연산부터 시작해야 한다는 것도 알고 있었습니다.
점화 유형
위의 규칙을 사용하여 찾을 수 있는 재귀 표현식은 다음과 같습니다.
(N을 1로 만드는 데 필요한 최소 횟수 = N-1을 1 + 1로 만드는 데 필요한 최소 횟수) 또는 (2 또는 3으로 나눌 때 나머지 몫 + 1에서 연산)
간단히 말해서 2와 3으로 나누어지지 않는다면 반드시 3번의 연산을 해야 하고, 나온 숫자에 최소한의 연산만 하면 됩니다.
2와 3 모두로 나눌 수 있는 경우 두 작업을 모두 수행하고 min 함수를 사용하여 더 작은 값을 선택합니다.
2로만 나눌 수 있거나 3으로만 나눌 수 있는 경우 맹목적으로 그 숫자로 나누지 말고 연산 3을 수행하는 경우를 고려하여 두 경우 모두 min 함수에 씁니다.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
int DP(1000000);
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);
}
}
cout << DP(N);
return 0;
}