1463번: 1로 만들기

문제:

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력:

첫째 줄에 1보다 크거나 같고, 10^6 보다 작거나 같은 정수 N이 주어진다.

풀이:

• 우선 다이나믹 프로그래밍을 풀 때는 점화식을 써 주는게 중요하다. 우리가 구하고자 하는 것부터 구하고자 하는 것을 얻기 위해서는 어떤 값이 필요한지 적어보자.
  • 구하고자 하는 것: 연산을 사용하는 횟수의 최솟값
  • 구하기 위해 필요한 것: 나누기 3, 2 / 빼기 1을 조합하여 나올 수 있는 모든 값 중 최솟값
• 이제 탑다운 방식과 바텀업 방식 중에 한가리를 골라야 되는데 나는 바텁업 방식을 사용하였다. 탑 다운 방식으로 풀면 x에서부터 모든 경우를 재귀함수로 1이 될 때까지 각 연산을 해주며 모든 연산 값을 종합하여 최솟값을 구하는 방식일 것이여서 너무 복잡할 것 같아서 바텀업 방식을 사용하였다. 바텁업 방식보다 직관적이여서 구현하기가 더 쉬울 것 같았다. 왜냐하면, 바텀업 방식은 1부터 시작하여 x를 만드는 것이므로 방식이며 각 이 전의 연산마다 최솟값이 항상 저장 되어 있을 것이며 그것을 호출하면 된다.
• 이제 필요한 것을 알았으니 점화식을 적어보자. 우선, 연산을 한번 할 때마다 더하기 1을 해줘야 되니 더하기 1이 들어가야겠고 다이나믹 프로그래밍은 예전에 저장한 값들을 이용하여야 되기 때문에 이전의 다양한 연산들 중에 횟수가 가장 적은 연산을 골라야 된다. 그렇게 해서 나온 식이 아래의 점화식이다.

$$ a_i = min(a_{i-1},a_{i/2},a_{i/3})+1 $$

• 이제 이 점화식을 코드로 구현하면 for문을 2부터 시작하여 x까지의 모든 연산의 횟수를 배열에 저장해주면서 올라갈 것이다. 꼭대기를 도달하기 위해 계단을 쌓아 올린다고 생각하면 편하다. 우리가 비교하여야 될 값들은 3가지이며 빼기 1의 연산은 2와 3으로 안나누어 지는 값일 경우에는 무조건 연산 되므로 제일 먼저 현재 값에 전의 수에 연산 횟수에 더하기 1을 해준다. 그러면 연산 횟수가 1 올라가면서 그 다음 값에 저장이 된다. 이제 이 값이 나누기 2 했을 때와 3 했을 때와도 비교해준다. min은 한번에 2개만 비교 가능하므로 우선 2, 3으로 나누어 떨어지는지 확인하고 나누어 떨어지면 배열에 저장 된 나누기 2, 3 했을 때의 값을 불러와 앞서 -1 했을 경우와 비교하여 최솟값을 저장하고 넘어간다.

코드:

#include <iostream>

using namespace std;

int main(){
	int x;
	//입력  
	cin >> x;
	//x 인덱스까지의 배열 생성 
	int dp[x+1] = {0, 0};
	//바텀 업 방식의 다이나믹 프로그래밍 구현
	for(int i = 2; i <= x; i++){ //바텀 업은 for문을 사용
		//입력값에서 1을 빼는 경우 저장
		dp[i] = dp[i-1]+1;
		//입력값에서 2를 나누는 경우와 비교하여 최소값 저장
		if(i % 2 == 0) dp[i] = min(dp[i], dp[i/2]+1);
		//입력값에서 3을 나누는 경우와 비교하여 최소값 저장
		if(i % 3 == 0) dp[i] = min(dp[i], dp[i/3]+1);
	}
	//출력 
	cout << dp[x];
}