[BOJ] 12852 "1로 만들기2" 문제 풀이 & 소스 코드 With C/C++

#INFO

난이도 :  SILVER1

알고리즘 유형 : DP

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

12852번: 1로 만들기 2

---

#SOLVE

DynamicProgramming 방식을 이용해 문제를 풀이했습니다.

dp[i] = i 를 1로 만드는 연산의 최솟값

before[i] = 연산 (1 or 2 or 3) 을 수행하기 직전의 i 값 . ex) before[10] = 9

before 배열은 N을 1로 만드는 방법에 포함되어 있는 수를 출력하기 위해 정의했습니다.

 

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

		before[i] = i - 1;
		if (i % 3 == 0 && dp[i] > dp[i/3] + 1) {
			dp[i] = dp[i/3] + 1;
			before[i] = i / 3;
		}

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

		if (i % 2 == 0 && dp[i] > dp[i/2] + 1) {
			dp[i] = dp[i/2] + 1;
			before[i] = i / 2;
		}

3. 1을 뺀다.

		dp[i] = dp[i-1] + 1;
		before[i] = i - 1;

 

위의 3가지 식을 비교하며 최소로 연산을 수행하는 값을 dp 배열에 저장한 뒤 n번째 dp값을 출력하면 됩니다.

---

#CODE

#include <iostream>
using namespace std;

int dp[1000001];
int before[1000001];

int main() {
  	int n;
	cin >> n;
	
	//init
	dp[0] = 0;
	dp[1] = 0;
	before[1] = -1;
	
	//dp
	for(int i = 2 ; i <= n ; i++) {
		dp[i] = dp[i-1] + 1;
		before[i] = i - 1;
		if (i % 3 == 0 && dp[i] > dp[i/3] + 1) {
			dp[i] = dp[i/3] + 1;
			before[i] = i / 3;
		}
		if (i % 2 == 0 && dp[i] > dp[i/2] + 1) {
			dp[i] = dp[i/2] + 1;
			before[i] = i / 2;
		}
	}
	
	cout << dp[n] << endl;
	cout << n << " ";
	while(before[n] != -1) {
		cout << before[n] << " ";
		n = before[n];
	}
	return 0;
}