BOJ 12852 1로 만들기 2

1 개요

BOJ 12852 1로 만들기 2

• 백준 온라인 저지 12852번 문제
• BOJ 34단계

2 같이 보기

• BOJ 1463 1로 만들기

3 C++

#include <iostream>
using namespace std;

int N;
int dp[1000001];
int visit[1000001];

void solve() {
    dp[0] = 0;
    dp[1] = 0;
    visit[1] = 0;
    for(int i=2; i<=N; i++) {
        dp[i] = dp[i-1]+1;
        visit[i] = i-1;
        if(i%3==0 && dp[i]>dp[i/3]+1) {
            dp[i] = dp[i/3]+1;
            visit[i] = i/3;
        }
        if(i%2==0 && dp[i]>dp[i/2]+1) {
            dp[i] = dp[i/2]+1;
            visit[i] = i/2;
        }
    }
}

int main() {
    cin >> N;
    solve();
    cout << dp[N] << '\n';
    int n = N;
    while(n) {
        cout << n << ' ';
        n = visit[n];
    }
}