mang_dev
맹꽁거리는 개발자
mang_dev
전체 방문자
오늘
어제
  • 분류 전체보기 (185)
    • Frontend (2)
      • Next.js (1)
    • Backend (3)
      • GraphQL (2)
    • Book (1)
      • 기타 (1)
    • Old (177)
      • 알고리즘 퍼즐 (1)
      • 백준 (131)
      • 프로그래머스 (0)
      • Codility (15)
      • LeetCode (7)
      • Codewars (1)
      • Codeforces (0)
      • Django (6)
      • React (2)
      • Naver Map Api (3)
      • Web UI (4)
      • Introduction to Cloud (2)
hELLO · Designed By 정상우.
mang_dev

맹꽁거리는 개발자

백준 16953번 A→B // C++
Old/백준

백준 16953번 A→B // C++

2020. 7. 30. 23:17

문제

A → B

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.


풀이

bfs 방식의 탐색을 통하여, A가 B가 될 수 있는지 확인한다.

해당 숫자를 작게 만드는 연산은 없기 때문에, 연산 결과가 B보다 큰 경우에는 탐색을 하지 않아도 된다.

1을 가장 오른쪽에 추가하는 연산은 (해당 수 * 10) + 1이다.

또한, B의 최대 값이 10^9인데 임의의 수 X*10가 int 범위를 벗어나는 경우가 생길 수 있으므로, X <= 10^8인 경우에만 10을 곱하는 연산을 하면 int의 범위를 벗어나지 않을 수 있다.


코드

#include <iostream>
#include <queue>

using namespace std;

#define MAXNUM 1000000000

int main() {
    int A, B;
    bool finish = false;

    cin >> A >> B;

    queue<pair<int, int>> q;
    q.push(make_pair(A, 1));

    while(!q.empty()){
        int num = q.front().first;
        int count = q.front().second;
        q.pop();

        if(num == B){
            cout << count;
            finish = true;
            break;
        }

        if(num * 2 <= B){
            q.push(make_pair(num * 2, count + 1));
        }
        if (num <= MAXNUM / 10) {
            if (num * 10 + 1 <= B) {
                q.push(make_pair(num * 10 + 1, count + 1));
            }
        }
    }

    if(!finish){
        cout << -1;
    }

    return 0;
}
저작자표시 (새창열림)

'Old > 백준' 카테고리의 다른 글

백준 1890번 점프 // C++  (0) 2020.08.12
백준 11053번 가장 긴 증가하는 부분 수열 // C++  (0) 2020.08.11
백준 9205번 맥주 마시면서 걸어가기 // C++  (0) 2020.07.30
백준 1991번 트리 순회 // C++  (0) 2020.07.30
백준 1408번 24 // C++  (2) 2020.07.15
    'Old/백준' 카테고리의 다른 글
    • 백준 1890번 점프 // C++
    • 백준 11053번 가장 긴 증가하는 부분 수열 // C++
    • 백준 9205번 맥주 마시면서 걸어가기 // C++
    • 백준 1991번 트리 순회 // C++
    mang_dev
    mang_dev

    티스토리툴바