BOJ 12852번: 1로 만들기 2

문제

문제 바로가기> BOJ 12852번: 1로 만들기 2

12852번: 1로 만들기 2

 

풀이

 

처음엔, 아래와 같이 dp 배열을 구축한 후,

구축된 배열에서 역추적해가며 N을 1로 만드는 방법에 포함되어 있는 수를 출력해주었다.

이 때는 ,, dp[1] = 0을 1로 초기화 해줘서 앞에서 리턴하게 하고 암튼 그랬지만,

전반적인 역추적 아이디어는 아래와 같았다.

 

그런데 사실 dp 배열을 만드는 과정에서 배열을 하나 더 만들어서 그 이전 값을 저장하는 dp 배열을 만든다면??!!

더 편하게 "N을 1로 만드는 방법에 포함되어 있는 수"를 구할 수 있다!!

dp 배열이 업데이트 됨에 따라 그 값을 담고 있는 배열도 함께 업데이트 될 테니까 ....!!

#include <iostream>
#define MAX 1000001
using namespace std;

int N;
int dp[MAX], before[MAX];

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

    dp[1] = before[1] = 0;
    for (int i = 2; i <= N; i++)
    {
        dp[i] = dp[i - 1] + 1;
        before[i] = i - 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
        {
            dp[i] = dp[i / 2] + 1;
            before[i] = i / 2;
        }
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
        {
            dp[i] = dp[i / 3] + 1;
            before[i] = i / 3;
        }
    }
    cout << dp[N] << "\n";
    while (N != 0)
    {
        cout << N << " ";
        N = before[N];
    }
}

 

사실 저 위에서 for문 말고 while문으로 돌면서, N/3, N/2, N-1을 그때 그때 봐주며 계산해도 된다.

그럼 메모리 더 적게 쓰고, 시간은 똑같기 때문!! 아래가 내가 짠 코드 중 제일 효율적인 코드였당

#include <iostream>
#define MAX 1000001
using namespace std;

int N;
int dp[MAX];

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

    dp[1] = 0;
    for (int i = 2; i <= N; i++)
    {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
            dp[i] = dp[i / 2] + 1;

        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
            dp[i] = dp[i / 3] + 1;
    }
    cout << dp[N] << "\n";

    int nextCnt = dp[N] - 1;
    while (N != 0)
    {
        cout << N << " ";
        if (N % 3 == 0 && dp[N / 3] == nextCnt)
            N /= 3;
        else if (N % 2 == 0 && dp[N / 2] == nextCnt)
            N /= 2;

        else
            N--;
        nextCnt--;
    }
}