[이코테] C++ 1로 만들기 - DP

문제

• 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
  • 1) X가 5로 나누어떨어지면, 5로 나눈다.
  • 2) X가 3으로 나누어 떨어지면, 3으로 나눈다.
  • 3) X가 2로 나누어 떨어지면, 2로 나눈다.
  • 4) X에서 1을 뺀다.
• 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.
• 연산을 사용하는 횟수의 최솟값을 출력하시오.
• 예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
  • 26 - 1 = 25
  • 25 / 5 = 5
  • 5 / 5 = 1

입력 조건

• 첫째 줄에 정수 X이 주어진다. (1<=X<=30,000)

출력 조건

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입력 예시

26

출력 예시

3

접근 방법

1. 예로 28은 14에서 2가 곱해졌을 수도 27에서 1이 더해졌을 수도 있다. 위 두 경우에서 더 적은 연산 수를 구하는 것이다.
   1) 28->14->7->6->2->1 : 총 5번
   2) 28->27->9->3->1 : 총 4번

   즉, 28은 27에 도달하는 횟수에 +1 한 것과 14에 도달하는 횟수에 +1한 것 중 작은 값을 택해야 한다.

2. 2부터 28까지 각 값에 도달하는 횟수를 저장해보면 될 것이다.
   ex) dp[2] = min(dp[1] + 1, dp[2/2] + 1)
   dp[28] = min(dp[27] + 1, dp[28/2] + 1)

풀이

#include <iostream>
#include <algorithm>
using namespace std;

int x;
int dp[30001];

int main() {
	cin >> x;

	for (int i = 2; i <= x; i++) {
		// 1을 빼는 경우
		// ex) i = 10, 10이 되기 위해선 9에서 1을 더하는 1번의 과정 필요
		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);
		
		if (i % 5 == 0)
			dp[i] = min(dp[i], dp[i / 5] + 1);
	}
	cout << dp[x] << "\n";

}