개요

백준 12852 (1로 만들기 2)

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

접근 방식

1. 단계가 분명히 나뉘어있고 최솟값을 구하는 문제이므로 다이나믹프로그래밍으로 접근했다.

2. 바텀업, 탑다운 방식을 모두 사용해서 풀었다.

바텀업 방식

1. 인덱스 1부터 반복문을 통해 증가해가며
   3을 곱한 값, 2를 곱한 값, 1을 더한 값을 전부 갱신해가며 인덱스 N까지 갱신해 준다.

2. 갱신할때 이전 값을 기록해야하므로 preNum배열을 생성했다.

3. prevNum배열은 인덱스숫자의 이전 숫자가 value에 저장된다.

탑다운 방식

1. Dp함수를 통해 재귀방식으로 분해했다.

2. Dp(int idx) 함수는

   • idx가 3으로 나눠떨어진다면 dp[idx]값을 Dp(idx/3)+1값과 비교해보고 적은 것으로 설정
   • idx가 2로 나눠떨어진다면 dp[idx]값을 Dp(idx/2)+1값과 비교해보고 적은 것으로 설정
   • dp[idx]값을 Dp(idx-1)+1값과 비교해보고 적은 것으로 설정

3. 위와 동일하게 prevNum배열 관리하며 이전 값 관리했다.

전체 코드(바텀 업)

#include<iostream>
#include<algorithm>
using namespace std;

int N;
int dp[1'000'002];
//value is prev num of idx
int prevNum[1'000'002];

int main(){
    cin>>N;
    fill(&dp[0],&dp[1'000'001],1'000'002);
    dp[1]=0;
    dp[2]=1;
    prevNum[2]=1;
    dp[3]=1;
    prevNum[3]=1;
    for(int i=1;i<N+1;i++){
        //max idx is 1'000'001
        if(i*3<=1'000'000){
            //if minimum num changed 
            if(dp[i]+1<dp[i*3]){
                //reassign
                prevNum[i*3]=i;
                dp[i*3]=dp[i]+1;
            }
        }
        //max idx is 1'000'001
        if(i*2<=1'000'000){
            //if minimum num changed 
            if(dp[i]+1<dp[i*2]){
                //reassign
                prevNum[i*2]=i;
                dp[i*2]=dp[i]+1;
            }

        }
        //max idx is 1'000'001
        if(i+1<=1'000'000){
            //if minimum num changed 
            if(dp[i]+1<dp[i+1]){
                //reassign                
                prevNum[i+1]=i;
                dp[i+1]=dp[i]+1;
            }
        }
    }
    cout<<dp[N]<<"\n"<<N<<" ";
    int tmpIdx=N;
    while(tmpIdx!=1){
        cout<<prevNum[tmpIdx]<<" ";
        tmpIdx=prevNum[tmpIdx];
    }
}

전체코드 (탑 다운)

#include<iostream>
#include<algorithm>
using namespace std;

int N;
int dp[1'000'002];
//value is prev num of idx
int prevNum[1'000'002];
int Dp(int idx) {
    int* ret = &dp[idx];
    if (*ret != 1'000'002) return *ret;
    if (idx < 1) return 0;
    int prevDp;
    if (idx % 3 == 0) {
        prevDp = Dp(idx / 3) + 1;
        if (*ret > prevDp) {
            prevNum[idx] = idx / 3;
            *ret = prevDp;
        }
    }
    if (idx % 2 == 0) {
        prevDp = Dp(idx / 2) + 1;
        if (*ret > prevDp) {
            prevNum[idx] = idx / 2;
            *ret = prevDp;
        }
    }
    prevDp = Dp(idx-1) + 1;
    if (*ret > prevDp) {
        prevNum[idx] = idx-1;
        *ret = prevDp;
    }
    return *ret;
}

int main() {
    cin >> N;
    fill(&dp[0], &dp[1'000'001], 1'000'002);
    dp[1] = 0;
    dp[2] = 1;
    prevNum[2] = 1;
    dp[3] = 1;
    prevNum[3] = 1;

    cout << Dp(N) << "\n" << N<<" ";
    int tmpIdx = N;
    while (tmpIdx != 1) {
        cout << prevNum[tmpIdx] << " ";
        tmpIdx = prevNum[tmpIdx];
    }
}

문풀후생

이상하게 늘 헷갈리는 부분은 마지막에 반복문 부분이다.

    int tmpIdx = N;
    while (tmpIdx != 1) {
        cout << prevNum[tmpIdx] << " ";
        tmpIdx = prevNum[tmpIdx];
    }

이렇게 반복문을 통해 어떤값이 1이 될때까지 반복하며 내려가는 구조가 늘 헷갈린다.
시작값과 끝값이 늘 의도와는 다른 것 같다.
따라서 끝 값과 시작값을 이중체크한다.