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

이희수·2024년 5월 28일

12852 DP 백준 알고리즘

알고리즘

목록 보기

11/25

문제

12852 1로 만들기 2

구상

X가 3으로 나누어 떨어지는 경우

X가 2로 나누어 떨어지는 경우

1을 빼는 경우

N이라는 자연수에 대하여 위의 3가지의 경우를 모두 탐색하여야 한다.
하지만 아래 2가지의 제약조건이 존재한다.

N은 최대 10^6 의 자연수이다.

연산의 최솟값을 구해야한다.

따라서 최적해를 이용하는 DP를 이용해서 문제를 풀어보자.

코드

#include<bits/stdc++.h> 
using namespace std;
const int INF = 987654321;
int n;
int dp[1000001];

int goDP(int num){
	// 탈출조건: num이 1에 도달 
	if(num==1) return 1;
	
	//메모이제이션 
	int &ret = dp[num];
	// ret에 최적해가 존재한다면 최적해를 기반으로 탐색함 
	if(ret) return ret;
	// 최솟값을 찾아야 하므로 최댓값으로 초기화한 후 탐색 
	ret = INF;
	
	// 가능한 경우의 수를 탐색하여 가장 작은 경우의 수를 찾음 
	if(num%3==0) ret = min(ret,goDP(num/3)+1);
	if(num%2==0) ret = min(ret,goDP(num/2)+1);
	if(num) ret = min(ret,goDP(num-1)+1);
	
	return ret;
}
void go(int num){
	// 출력 
	cout<<num<<" ";
	
	// 다음 최적해 찾기 
	if(num%3==0 && dp[num/3]==dp[num]-1) go(num/3);
	else if(num%2==0 && dp[num/2]==dp[num]-1) go(num/2);
	else if(num-1 >= 1 && dp[num-1]==dp[num]-1) go(num-1); 
	
	return;
}
void go(int num);
int main() {
	cin>>n;
	// 연산횟수 최솟값 찾기 
	cout<<goDP(n)-1<<'\n';
	
	// goDP에서 1일경우 return 되므로 dp[1]의 값이 존재하지않음 
	// go()의 종착점인 dp[1]의 값을 1으로 설정 
	dp[1]=1;
	
	// dp를 추적해서 최적해인 수 출력 (trace) 
	go(n);
	return 0;
}

goDP()

우선 연산횟수의 최솟값을 찾는 goDP부터 살펴보자.

탈출조건 정의

먼저 탈출조건을 정의한다.

int goDP(int num){
	// 탈출조건: num이 1에 도달 
	if(num==1) return 0;
}

현재 어떤 값을 return할지 정하지 않았으므로 return 0으로 정의해둔다.

메모이제이션

다음으로 메모이제이션을 진행한다.
메모이제이션을 모른다면?

int goDP(int num){
	// 탈출조건: num이 1에 도달 
	if(num==1) return 0;
	
	//메모이제이션 
	int &ret = dp[num];
	// ret에 최적해가 존재한다면 최적해를 기반으로 탐색함 
	if(ret) return ret;
	// 최솟값을 찾아야 하므로 최댓값으로 초기화한 후 탐색 
	ret = INF;
}

최적해를 저장해둔 dp 배열에 접근하여 해당 원소에 값이 존재한다면 최적해가 존재하는 것이므로 그 값에 대한 탐색을 중단하고 그 값을 리턴해준다.

int &ret = dp[num];
if(ret) return ret;

dp에 값이 존재하지않는다면 가장 큰 값인 INF로 ret을 초기화해준다.

ret = INF;

로직

X가 3으로 나누어 떨어지는 경우

X가 2로 나누어 떨어지는 경우

1을 빼는 경우

문제의 조건에 따라 위 경우를 탐색한다.
하지만 우리는 가장 작은 경우의 수를 구하고 있기 때문에, 최솟값을 구해야한다.

따라서 탐색한 값의 최솟값을 저장한다.

// case1
if(num%3==0) ret = min(ret,goDP(num/3)+1);
// case2
if(num%2==0) ret = min(ret,goDP(num/2)+1);
// case3
if(num) ret = min(ret,goDP(num-1)+1);

이제 위 탈출조건의 return 값을 정할 수 있을것이다.
위 탐색을 살펴보면 우린 경우의 수를 구하고 있으므로 최종값인 1에 도달시 1을 return 해야한다는 것을 알 수 있다.

이렇게 아래와 같이 goDP 함수를 완성할 수 있다.

int goDP(int num){
	// 탈출조건: num이 1에 도달 
	if(num==1) return 1;
	
	//메모이제이션 
	int &ret = dp[num];
	// ret에 최적해가 존재한다면 최적해를 기반으로 탐색함 
	if(ret) return ret;
	// 최솟값을 찾아야 하므로 최댓값으로 초기화한 후 탐색 
	ret = INF;
	
	// 가능한 경우의 수를 탐색하여 가장 작은 경우의 수를 찾음 
	if(num%3==0) ret = min(ret,goDP(num/3)+1);
	if(num%2==0) ret = min(ret,goDP(num/2)+1);
	if(num) ret = min(ret,goDP(num-1)+1);
	
	return ret;
}

그러나 이 문제는 연산의 최솟값과 그 최솟값에 해당하는 방법에 포함되어있는 수를 출력해주어야 한다. 어떻게 출력해야할까?

예를 들어 N이 9인 경우를 생각해보자.

9가 1이되는 연산의 최솟값은 9 -> 3-> 1일것이다.
그렇다면 dp[9], dp[3], dp[1]에는 각각 3,2,1 이 저장되어 있을것이다.
이 점을 이용해보자.

go()

void go(int num){
	// 출력 
	cout<<num<<" ";
	
	// 다음 최적해 찾기 
	if(num%3==0 && dp[num/3]==dp[num]-1) go(num/3);
	else if(num%2==0 && dp[num/2]==dp[num]-1) go(num/2);
	else if(num-1 >= 1 && dp[num-1]==dp[num]-1) go(num-1); 
	
	return;
}