[알고리즘] C++ 백준12852 1로 만들기 2

백준 12852

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

풀이 전 나의 생각

어느 연산 과정을 통해 최솟값을 구해야 하는 문제들은 대부분 역추적을 이용하면 한층 더 쉽게

접근 할 수있다. 

 

문제의 연산 조건을 보면

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

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

3. 1을 뺀다.

 

여기서 알 수 있는건 지정한 수의 연산과정 최대값 즉, 최악의 값은 계속 1을 빼주는 것이다.

그렇기 때문에 DP의 초기값을 모두 자신의 값으로 넣어준다. ex) dp[1] = 1, dp[2] = 2, dp[3] = 3....

요약하자면 연산조건 1, 2번을 무시하고 3번만 진행했을 때 1의 최대 과정 수는 1, 2는 3번 과정이 추가된 2, 3은 3번과정이 추가된 3... 이렇게 과정의 값이 하나씩 증가하는 것이라고 보면된다.

 

다음으로 각 연산 조건마다 과정의 최솟값을 구해야 한다. 0과 1은 연산할 필요가 없기 때문에 2부터 n까지 진행한다.

 

dp[i] = min(dp[i], dp[i / 2]);

i가 2로 나누어 질 때 (2번 조건) 실행하는 점화식이다.

만약에 i가 4라고 가정하면 dp[4 / 2] = dp[2]가 나올 것이다.

이 과정을 해주는 이유는 지금은 dp[4]의 최소가 되는 과정 값을 구해야 하기 때문이다.

그러니 4를 2로 나눈 dp[2] 즉, 2일 때 나올 수 있는 최소 과정 값을 구해 놓는다.

 

마찬가지로 i가 3으로 나누어질 때 똑같은 과정을 거치면된다. 그러면 최종적으로 전 단계의 최소 과정 값은 다 구해진 상태일 것이다.

 

dp[i] = min(dp[i], dp[i - 1]) + 1;

그럼 이제 전 단계의 최소 과정값에 현재 과정을 진행 했다는 표시를 해줘야 하니 +1을 더해준다.

dp[i] 와 dp[i - 1]의 최솟값을 구하는 이유는 내가 1, 2번 조건을 거쳐서 얻은 전 단계의 최소 과정값과 3번 조건을 거쳐서 얻은 전 단계의 최소 과정값을 비교해야 하기 때문이다.

 

이렇게 연산조건 3단계를 모두 거쳐서 나온 DP값, 즉 과정의 최소값을 모두 구해줄 수 있다.

 

그러면 마지막으로 과정을 보여주어야 한다.

역추적으로 값을 얻어냈으니 반대로 값을 보여줄 땐 처음 값 부터 차근차근 내려가며 출력을 해주면된다.

 

dp[n] == dp[n - 1] + 1

지금 단계의 최소 과정값이 전 단계의 최소 과정값에 한 단계를 더 추가해준 값이라면 

그 과정을 거쳤다는 것이 확정되기 때문에 진입하여 상황에 맞는 값을 출력해주면된다.

위의 식은 3번 조건일 경우이기 때문에 현재 n값에 -1을 빼준 값을 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;

int n, dp[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		dp[i] = i;
	}
	
	for (int i = 2; i <= n; i++)
	{
		if (i % 2 == 0)
		{
			dp[i] = min(dp[i], dp[i / 2]);
		}
		if (i % 3 == 0)
		{
			dp[i] = min(dp[i], dp[i / 3]);
		}

		dp[i] = min(dp[i], dp[i - 1]) + 1;
	}

	cout << dp[n] - 1 << '\n';

	while (n != 0)
	{
		cout << n << ' ';

		if (dp[n] == dp[n - 1] + 1)
		{
			n -= 1;
		}
		else if (n % 2 == 0 && dp[n] == dp[n / 2] + 1)
		{
			n /= 2;
		}
		else 
		{
			n /= 3;
		}
	}
}