[틀림] 백준 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;

}

 

* 2회독( 25.3.15.)

• 경로복원방법
  • dp 값의 특징을 관찰
  • dp값이 1차이나는것이 최적!
  • 후보값들(/3, /2 -1)에 대해 차이가 1나는지 검사하고, 맞다면 거기로 들어가면 된다.
  • 리프노드도 return 0 전에 dp[n]=0으로 기록해줘야함.

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

typedef long long ll;

int n;
ll dp[1000000+4];

ll dfs(int n) {
   if(n==1) {
      dp[n]=0; // 리프노드도 기록해야 추적가능
      return 0;
   }
   
   ll & ret = dp[n];
   if(ret!=987654321+1) {
      return ret;
   }

   ret=987654321;
   if(n%2==0) {
      ret = min(ret,dfs(n/2)+1);
   }
   if(n%3==0)
      ret = min(ret,dfs(n/3)+1);
   ret = min(ret,dfs(n-1)+1);
   return ret;
}

void trace(int here) {
   if(here==0) return;
   cout<<here<<" ";
   if(here%3==0 && dp[here] == (dp[here/3]+1)) trace(here/3);
   else if(here%2==0 && dp[here] == (dp[here/2]+1)) trace(here/2);
   else if((here-1>=0) && (dp[here] == dp[here-1]+1)) trace(here-1);

   return;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   
   cin>>n;
      
   fill(dp,dp+1000000+4,987654321+1);
   
   cout<<dfs(n)<<"\n";
   // for(int i=0;i<=n;++i) {
   //    cout<<dp[i]<<" ";
   // }cout<<"\n";
   trace(n);
}