1463번

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


int main()
{
	int dp[1000001];
	int n;
	cin >> n;
	
	dp[0] = 0;
	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);
		}
	}
	cout << dp[n];
}

 

dp란 dynamic programming 으로써 동적 프로그래밍이다

 

사람들은 dp란 문제를 해결할때 큰 틀에서 작은 틀로 좁혀가는것이 아닌 작은 문제부터 해결하여

그 작은 문제를 기반으로 점점 큰 문제까지 해결해나가는 방법이라고한다.

 

이  문제 또한 dp 방식으로 문제를 해결해나갔다.

 

n이 주어졌을때 

 

1.n-1

2.n/2

3.n/3

 

이 세가지 방식을 활용하여 1까지 만들어 나갈때 계산식을 몇번 수행하면 1이 나오는지

그리고

그 수행 횟수가 가장 작은 수는 몇인지를 묻는 문제이다.

 

자!

 

먼저 n의 계산식 횟수를 구하기 전에 가장 작은 수 0 과 1 부터 몇번의 계산식을 수행해야 1이 나오는지 구해보자.

고등학교를 졸업한 사람이라면 쉽게 해결할 수 있다.

 

0과 같은경우 1이 될 수가 없다. 따라서 0번이다.

1과 같은 경우 이미 1이 되어있기때문에 0번이다.

 

이 횟수를 나는 dp라는 배열(테이블)에 저장해둘것이다.

 

dp[0] = 0;

dp[1] = 0;

 

자 다음 n이 2가 되었을땐 어떻게 최소 계산식 수행 횟수를 구할 수 있을까?

n이 2일땐 1을 만들기위해 2가지 방법이 있다.

 

첫번째 방법

2 - 1 = 1

 

두번째 방법

2/2 = 1

 

이때 서두에서 주어진 3을 나누는 방식도 있지만 2는 3으로 나누어지지 않기때문에 건너뛴다.

 

우리는 이제 첫번째 방법과 두번째 방법중 최소값을 구할것이다. 그리고 그 방식을 dp[2]에 저장할것이다.

 

첫번째 방법의 횟수를 구하기 위한 식은 이렇게 된다.

dp[2] = dp[i-1] + 1 이를 풀어보면 dp[2] = dp[1] + 1 이다.

 

여기서 1을 왜 더하지? 라고 생각할 수 있다. 그 이유는 2에서 1을 뺌으로써 계산식 1번을 수행하기때문에

1을 더하게된다.

 

자 다시 식을 살펴보자

dp[2] = dp[1] + 1이다.

즉 2가 1이 되기 위해 수행해야하는 최소 계산식 수행 횟수는 dp[1] + 1이라는 소리이다. 

 

여기서 

 

dp[1]은 1이라는 숫자가 1이 되기 위한 최소 계산식 수행 횟수를 의미한다.

우리는 dp[1] 의 값을 서두에서 미리 구해놓았다. 

 

1이 1이 되기위해선 0번을 수행한다.. 이미 1이기때문이다.

우리는 dp[1] + 1 식을 계산하여 dp[2] 즉 2가 1이 되기 위한 최소 계산식 수행 횟수를 구하게되었다. 

 

다음으로 두번째 방법의 횟수를 구해보겠다.

 

dp[2/2] + 1;

2를 2로 나누면 1이된다.

dp[1] + 1

이 또한 갯수가 총 2개이다.

첫번째 식과 두번째 식의 최소값을 구하려 했지만 둘다 2이기때문에

dp[2] 에는 2를 저장해둔다.

 

n이 3일때 또한 이런 방식으로 수행하여 최소값을 dp[3]에 저장해둔다. 

 

계산식을 수행해보면 dp[3]에 1이 저장된다.

다음 n이 4일때의 경우를 계산해보자.

 

첫번째 경우

dp[4] = dp[3] + 1;  dp[3]은 1이기때문에 dp[4] = 2가 주어진다.

두번째 경우

dp[4/2] + 1; dp[2]또한 1이기때문에 이 방법또한 값이 2이다.

 

dp[4] = 2 저장

 

n이 5일때

첫번째 경우

dp[5] = dp[4] + 1; dp[4]는 2이기때문에 dp[5] = 3이 주어진다. 2와 3으로 나눠지기않기때문에 다음으로 넘어간다.

 

n이 6일때

첫번째 경우

dp[6] = dp[5] + 1 (dp[6] = 4)

 

두번째 경우

dp[6/2] + 1 (dp[3] + 1 = 2)

 

세번째 경우

dp[6/3] + 1 (dp[2] + 1 = 2)

 

세가지 경우중 가장 작은 값은 총 2번 

 

dp[6] = 2

 

이런식으로 n의 최소 계산식 수행 횟수를 구하기 위해선 이전에 수행하여 구한 횟수들을 활용한다.

 

이것이 바로 dp 방식이다.