문제 출처

1. 문제설명

  • 정수 X를 1로 만드는 최소한의 방법과 그 수를 출력하라
  • 사용 가능한 연산
    • X가 3으로 나누어 떨어지면 3으로 나눈다.
    • X가 2로 나누어 떨어지면 2로 나눈다.
    • 1을 뺀다.



2. 알고리즘 설계

  • 시간 제한이 0.5초이므로, DP 외에 떠오른 방법이 없다.
  • 1을 빼준 값으로 DP 배열을 초기화 시킨다.
  • 기존 연산 수, 2로 나눴을 때의 연산 수, 3으로 나눴을 때 연산 수 중 작은 값으로 갱신
  • 위치를 기억해야 하므로, 위치도 각 연산에 맞게 설정한다.
    • i/2라면 pre[i] = i/2



3. 전체 코드

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

const int SZ = 1000001;
int n, DP[SZ], pre[SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	DP[1] = 0;
	for(int i=2; i<=n; i++) {
		DP[i] = DP[i-1] + 1;
		pre[i] = i-1;

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

		if(i%3 == 0 && DP[i] > DP[i/3]) {
			DP[i] = DP[i/3] + 1;
			pre[i] = i/3;
		}
	}

	cout << DP[n] << '\n';
	
	int idx = n;
	while(true) {
		cout << idx << ' ';
		if(idx == 1) break;
		idx = pre[idx];
	}

	return 0;
}