백준 1463: 1로 만들기

문제

문제 링크: https://www.acmicpc.net/problem/1463 

이 문제의 경우, 입력값에 대해 2로 나누어지는 값이라면 2로 나누고, 3으로 나누어 지는 값이라면 3으로 나눕니다. 

두가지에도 포함이 되지 않는다면, 1을 빼어 1이 될 때 까지 연산을 합니다. 

이때, 연산을 최소한으로 하는 방법을 구하는 문제로, 다이나믹 프로그래밍을 사용하면 간단히 풀 수 있습니다. 

저의 경우는 Top-Down 방식으로만 풀어 올렸지만, Bottom-Up 방식으로도 해보는 것을 추천합니다.

다이나믹 프로그래밍에서는 점화식을 찾아내는것이 가장 중요합니다.

해당 문제의 점화식의 경우는 3가지로 나눌 수 있으며, 선택지가 많을 경우 저장된 값을 확인 후에 저장 된 값보다 새로운 값이 작다면

이를 저장하는 방식으로 진행합니다.

<점화식>

• f(n/3) +1 (n이 3으로 나누어질 경우)
• f(n/2) +1 (n이 2으로 나누어질 경우)
• f(n-1) +1 (위에 해당 사항이 없는 경우, 모든 경우에 이에 해당한다)

+1을 해준 이유는 연산이 진행 될 때 마다 횟수를 체크해야 하므로 꼭 들어가야합니다.

만약 n이 1이라면, 당연히 답은 0이 됩니다.

코드

#include <iostream>
 
using namespace std;
 
int d[1000001];        //구한 값 저장 공간
 
int one(int n){
    if(n == 1) return 0;    //n이 1일떄, 0으로 반환
    if(d[n]>0) return d[n];    //해당 저장 공간에 값이 존재 할 경우, 그 값으로 반환. <가장 중요한 부분!>
    
    d[n] = one(n-1)+1;
 
    //2로 나눌 수 있을 경우
    if(n%2 == 0){
        int temp = one(n/2)+1;
        if(d[n]>temp) d[n] = temp;
    }
 
    //3으로 나눌 수 있을 경우
    if(n%3 == 0){
        int temp = one(n/3)+1;
        if(d[n]>temp) d[n] = temp;
    }
    return d[n];
}
 
int main(){
    int N;
    cin >> N;
    cout << one(N) <<"\n";
    return 0;
}