[DP] 1463번 문제풀이

문제분석

문제는 이렇습니다.

임의의 숫자를 3가지의 연산을 이용하여 1을 만들고자 할때,

연산횟수의 최솟값은 ?!

 

1. X가 3으로 나누어 떨어지는 경우, 3으로 나눈다.

2. X가 2로 나누어 떨어지는 경우, 2로 나눈다.

3. X 에 1을 뺀다.

 

예를 들어, 12이라는 숫자가 주어졌고

같이 1로 만들어 봅시다.

 

첫번째

12 > 4 > 2 > 1

총 3회

 

두번째

12 > 6 > 3 > 1

총 3회

 

이런식으로 3가지의 연산을 사용하면

다양한 경우의 수가 등장합니다.

 

그러면 이 경우의 수를 모두 따져봅시다.

 

d[i] = i 를 1로 만드는 최소 연산 횟수

라고 정의합시다.

 

 

1. x가 3으로 나누어 떨어지면, 3으로 나눈다.

d[12] = d[12/3] + 1

현재, 12는 3으로 나누어 떨어지므로

3으로 나눈 값의 최소 횟수에 1을 더한값을 배열에 넣어주는 것입니다.

2. x가 2로 나누어 떨어지면, 2로나눈다.

d[12] = d[12/2] + 1

12는 2로 나누어 떨어지므로 2로 나눈 값의 최소 횟수에 1을 더한값을 

배열에 넣어줍니다.

3. x에 1을 빼준다.

d[12] = d[12 -1] + 1

11의 최소 횟수에 1을 더해준다. 

계속 1을 더해주는 것은 연산을 한번 진행했기 때문인거 아시죠 ?

이제 이 세가지 경우의 최솟 값을 찾아야 합니다.

그런데, 1번, 2번의 경우는 중복되지 않기 때문에

3번이랑만 비교하면 되겠죠 ?

 

따라서 3으로 나누어 지는 경우는 1번과 3번을 비교하고

2로 나누어지는 경우는 2번과 3번을 비교하면 됩니다.

 

마지막으로 d[1]의 경우는 0으로 초기화를 해주셔야되요. 

1은 이미 1이기 때문에 당연히 연산이 필요없겠죠.

 

코드

#include <bits/stdc++.h>

using namespace std;
int d[1000000];
int n;
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	d[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
	}
	cout << d[n];

}