백준 12852 1로만들기 2 c++ // dp, 경로복원 하는 방법 pre[i]

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

12852번: 1로 만들기 2

1. 경로복원 하는 방법(1) : 

pre[i] : i는 pre[i]로 가는게 최선이다.

pre[3] =1  : 3은 1로 가는게 최선임.

 

2.바킹독 코드

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/da0497aabb26436c9ae613785cb439f7
#include <bits/stdc++.h>
using namespace std;

int d[1000005]; //d[i] : i를 1로만드는데 필요한 연산의 최소값
int pre[1000005];
// pre[i] : i는 pre[i]로 가는게 최선이다. / pre[i]=i로 가기위해 선택한 연산
//pre[3]=1  -> 3은 1로가는게 최선임.
int n;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    d[1] = 0;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + 1;
        pre[i] = i - 1;
        if (i % 2 == 0 && d[i] > d[i / 2] + 1) {
            d[i] = d[i / 2] + 1;
            pre[i] = i / 2;
        }
        if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
            d[i] = d[i / 3] + 1;
            pre[i] = i / 3;
        }
    }
    cout << d[n] << '\n';
    int cur = n;
    while (true) {
        cout << cur << ' ';
        if (cur == 1) break;
        cur = pre[cur];
    }
}

 

3. 내코드

d2[i][j] : 경로복원용 테이블

#include <bits/stdc++.h>
using namespace std;

/*
* DP
* 1. 테이블정의
* 2. 점화식 for문
*/

/*
* 1. 테이블정의
* d[i] : i를 1로만드는데 필요한 연산의 최소값 
* d2[i][j] : i를 1로만드는데 필요한 연산의 최소값 
/ 그때사용한 연산 j(1:-1 , 2:/2 , 3:*3)
* 

2.점화식
d[k] = 
3로 나누어떨어지는 경우 : d[k/3]+1
2로 나누어떨어지는 경우 : d[k/2]+1
d[k-1]+1 
중 최소값


3.초기값 정하기
d[1] = 0
d[2] = 1
d[3] = 1

*/

int d[1000004] , d2[1000004][4];
int n;
int ret = 10000009;

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

	cin >> n;

	d[1] = 0;
	d[2] = 1;
	d[3] = 1;

	d2[1][0] = 0;
	d2[2][2] = 1;
	d2[3][3] = 1;



	for (int i = 4; i <= n; ++i) {
		int op = 1;
		d[i] = d[i - 1] + 1;
		if (i % 3 == 0) {
			if (d[i] > d[i / 3] + 1) {
				op = 3;
				d[i] = d[i / 3] + 1;
			}

		}
		if (i % 2 == 0) {
			if (d[i] > d[i / 2] + 1) {
				op = 2;
				d[i] = d[i / 2] + 1;
			}
		}

		if (op == 1) {
			d2[i][1] = 1;
		}
		else if (op == 2) {
			d2[i][2] = 1;

		}
		else if(op==3){
			d2[i][3] = 1;

		}

	}
	
	cout << d[n]<<"\n";
	cout << n << " ";
	while (n != 1) {
		if (d2[n][1]) {
			n--;
			cout << n << " ";
		}
		else if (d2[n][2]) {
			n/=2;
			cout << n << " ";
		}
		else if (d2[n][3]) {
			n/=3;
			cout << n << " ";
		}
	}

	return 0;

}