백준 | 1463. 1로 만들기

 

처음에는 그냥 조건에 맞게 대충 순서대로 조건만 넣어서 이렇게 실행해봤는데

#include <iostream>
using namespace std;

int main(){
    int x;
    int ans = 0;
    cin >> x;
    while(x>1){
        switch(x%3){
            case 0:
                if(x%9==0){x/=9; ans+=2;}
                else {x/=3; ans++;}
                break;
            case 1 : x--; ans++; break;
            case 2 :
                if(x%2==0) x/=2;
                else x-=1; 
                ans++;
                break;
        }
        //cout << x << ";;;";
    }
    cout << ans;
}

 

당연히 될리가 없슨....

용량이나 시간도 당연히 문제지만 제대로 된 답이 안나옴

 

그래서 고민한게

이런식으로 dp를 활용해서 풀어보는 것!

idx를 가지고 그거/2, /3하는거랑

vector 값 /2, /3하는거

vector값--하는거 중

작은거를 넣는 방식으로 해나가는거지

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

int main(){
    int n;
    cin >> n;
    vector <int> v (n+1, n);
    int idx = n;
    while(v[idx]>1){
        int num = idx%3==0? idx/3 : idx%2==0? idx/2 : idx;
        int num2 = v[idx]%3==0? v[idx]/3 : v[idx]%2==0? v[idx]/2 : idx;
        v[idx-1] = min(v[idx]-1, num, num2);
        idx--;
    }
    cout << n-idx;
}

이렇게 하니까 오류가 나왔는데 뒤에서부터 계산하니까

사실상 아까랑 다를게 없고

dp를 제대로 활용한게 아니라서.....

 

그럼 dp를 어떻게 활용해야하나 고민한 결과가

---

 

dp[i] = 정수 i를 1로 만드는 최소 연산 횟수

dp[1] = 0 (1은 이미 1이므로 연산이 필요 없음)

dp[i] = dp[i - 1] + 1
if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1)
if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1)

1을 빼는 경우 (i - 1) // 2로 나누는 경우 (i / 2) // 3으로 나누는 경우 (i / 3)
이 세 가지 중 최소값을 선택하면 된다.

각 숫자마다 최대 3번의 연산만 수행하므로
O(n) 으로 매우 빠르게 동작할 수 있음.

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

int main(){
    int n;
    cin >> n;
    vector <int> dp(n+1, 0);
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1]+1;
        if(i%2==0) dp[i] = min(dp[i], dp[i/2]+1);
        if(i%3==0) dp[i] = min(dp[i], dp[i/3]+1); 
    }
    cout << dp[n];
}

 그렇게 드디어 성공!!!!

 

dp 자체가 약간

저장하고 예전에 저장해둔걸 불러와서 활용하는 넉낌이라고 생각하고

문제에 접근하면 조금 더 쉽게 풀릴 것 같다

 

dp문제 하나 더 풀어봐야지