[DP] 1463번 1로 만들기

1463번 1로 만들기

 

https://www.acmicpc.net/problem/1463

 

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

예제 입력

10

 

예제 출력

3

 

해결방법

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

⭐️ 솔루션 ⭐️

백준 DP 파트 수업을 들으며 풀었던 문제이다.

DP를 처음 접한터라 백준님의 솔루션대로 문제를 해결하였다. (Top-down 방식)

N = 10 이라면 3가지 경우를 모두 재귀로 호출한다.

D[10] 은 D[9]+1 , D[5]+1 의 최소값을 저장한다. 또한 D[9] 또한 D[8]+1 , D[3]+1 의 최소값을 저장한다.

이런식으로 memoization 을 수행한 뒤, D[10] 을 출력하면 정답을 찾을 수 있다.

 

[ Top-down ]

int dp(int nn){
    if(nn==1) return 0;
    if(d[nn] != 0) return d[nn];
    
    d[nn] = dp(nn-1) + 1;
    if(nn % 3 == 0){
        tmp = dp(nn/3) + 1;
        if(d[nn] > tmp) d[nn] = tmp;
    }
    if(nn % 2 == 0){
        tmp = dp(nn/2) + 1;
        if(d[nn] > tmp) d[nn] = tmp;
    }
    
    return d[nn];
}

 

✅ 추가 수정 !!

DP 를 새로 공부하면서 Bottom-Up 방식으로 코드를 수정하였다

d[n] = min(d[n/3], d[n/2], d[n-1]) + 1 이라는 순환식을 이용해서 for 문을 사용했다

 

 

 

소스코드

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 1000001
using namespace std;

int n;
int d[MAX];

/*
 
 순환식 : d[n] = min(d[n/3], d[n/2], d[n-1]) + 1
 
 */

void dp(){
    d[1] = 0;
    
    for(int i=2; i<=n; i++){
        // 1을 뺌
        int res = d[i-1] + 1;
        
        // 3으로 나누어 떨어진다면, 3으로 나눔
        if(i%3 == 0){
            res = min(res, d[i/3]+1);
        }
        
        // 2으로 나누어 떨어진다면, 2으로 나눔
        if(i%2 == 0){
            res = min(res, d[i/2]+1);
        }
        
        d[i] = res;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    dp();
    
    cout << d[n] << "\n";
    
    return 0;
}