[백준] 16953번: A → B (C++)

 

그리디 알고리즘 문제는

코드 자체가 길진 않았다

다만 어떻게 구현해서 정확한 값을 도출할 지가 관건이다

 

DFS, BFS 에 대한 스터디를 진행하지 않아

조금 찾아보고 풀어 본 문제

 

두 수를 입력 받고 n을 m으로 바꾸기 위해 가능한 연산은 두 가지

2를 곱하거나 ,1을 수의 가장 오른 쪽에 추가한다

이 말은 즉 곱하기 10 더하기 1이다

 

처음에는 n을 m으로 바꿀 방법을 모색하다가

경우의 수를 둬서 풀었을 때

while 문 두 번에 시간 초과가 뜰 것 같아

m에서 n을 접근하는 방법으로 변경했다

 

위 두 가지 연산을 반대로 하면

2를 나누거나, 10을 나누는 것이다

10을 먼저 나누는 것이 변경 횟수가 줄어드므로

10을 먼저 나눈 후, 2를 나눌 수 있는지 여부를 확인한다

 

만약 두 수로 나눌 수 없거나 애초에 값이 크면 -1 을 출력하도록 설정한다

// baekjoon 16953

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int main(){
    init();
    
    int n, m;
    cin >> n >> m;
    
    int opt = 0;
    int count = 0;
    int min_count = 0;
    
    while (n != m) {
        if(n > m){
            count = -2;
            break;
        }
        else if (m % 10 == 1){
            m = m / 10;
            count++;
        }
        else if (m % 2 == 0){
            m = m / 2;
            count++;
        }
        else{
            count = -2;
            break;
        }
    }
    
    cout << (count + 1);
}

발제에서 진행했던 것처럼

그리디 알고리즘은 구현이 간단하다는 장점이 있다

그만큼 빠르게 작동하지만

정확히 구현해야 최적해를 구할 수 있다