백준 12852번 1로 만들기 2

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/12852

 

 

 

12852번: 1로 만들기 2

 

 

이번 문제는 다이나믹 프로그래밍(DP) 문제였습니다.

 

1463번 1로 만들기 문제와 다른 점은 n을 1로 만드는 방법에 포함되어 있는 수들을 역추적하여 출력하면 됩니다. 😛 

 

 

 

 

 

《문제 풀이》

 

1 ~ n 의 각 숫자를 1로 만들기 위해 연산을 하는 횟수의 최솟값을 dp 배열에 저장하려고 함 

 

1. 숫자 1의 연산 횟수의 최솟값은 0 이므로 dp[1] = 0

2. 1의 이전 경로는 존재하지 않으므로 before[1] = -1 (경로 추적을 위한 배열 before)

3. 정수 n에 사용할 수 있는 세 가지 연산 중 1을 빼는 연산은 항상 가능

4. 해당 숫자가 2로 나누어 떨어지거나 3으로 나누어 떨어지면 연산 횟수의 최솟값과 경로 갱신

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 1000001

using namespace std;

int n;
int dp[MAX], before[MAX];

void makeOne() {
	dp[1] = 0;
	before[1] = -1; // 경로 없음 
	
	for(int i=2; i<=n; i++) {
		// 1을 빼는 연산  
		dp[i] = dp[i - 1] + 1;
		before[i] = i - 1;
		
		// 2로 나누어 떨어지면  
		if(i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
			dp[i] = dp[i / 2] + 1;
			before[i] = i / 2;
		}
		
		// 3으로 나누어 떨어지면 
		if(i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
			dp[i] = dp[i / 3] + 1;
			before[i] = i / 3;
		} 
	} 
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	makeOne();
	
	// 연산 횟수의 최솟값  
	cout<<dp[n]<<"\n";
	
	int idx = n;
	while(idx != -1) {
		cout<<idx<<" ";
		idx = before[idx];
	}
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면