[C언어 백준 풀이] 16953번 : A → B (탐색, BFS 없는 풀이)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 Class 4 문제에 해당하는 16953번 : A → B에 대한 풀이 코드와 해설을 포함하고 있습니다.

 

 

그동안 낮은 티어 문제들 중 의미 없는 것들은 딱히 다루지 않고 풀고 있었는데 이 문제의 경우에는 알고리즘 분류나 다른 사람들의 풀이가 필요 이상으로 어렵게 작성되어 있는 경우가 많아 제가 더 간단한 방법으로 풀이를 작성하게 되었습니다.

 

 

16953번 : A → B

 

정수 A를 B로 바꾸려는 과정에서 2를 곱하거나 10을 곱하고 1을 더하는 연산 두 가지 중 하나를 선택해 나가면서 몇 번의 연산 안에 변환이 가능한지 출력하는 문제입니다.

뒤에 1을 붙이는 것은 10을 곱하고 1을 더한다는 의미로 해석하면 되겠습니다.

거치는 모든 수에서 2가지의 선택지가 있기 때문에 경우의 수가 연산을 해나감에 따라 기하급수적으로 늘어나게 됩니다.

또한 두 연산 모두 수를 증가시키는 연산이기 때문에, 모든 수를 만드는 것은 불가능하므로 불가능한 경우도 판정할 수 있는 알고리즘이 필요합니다.

이 문제의 힌트 부분을 보면 알고리즘 분류가 다음과 같이 되어있습니다.

 

 

물론 그래프 이론을 이용해서 BFS로 풀이할수도 있겠지만, 사실 이 문제는 탐색을 사용하기에는 너무 과한 문제입니다.

왜냐하면 대략적으로 범위와 연산 수를 계산해보면 A = 1, B = 10^9로 잡더라도 2의 거듭 제곱으로는 연산이 많이 이루어지겠지만 10을 곱하고 1을 더하는 연산은 몇 번 발생하지 않습니다.

그렇기 때문에 이것은 단순히 2의 거듭제곱 꼴로 연산 시간이 늘어난다고 생각하면 안된다는 것입니다.

따라서 범위를 제한하고 재귀함수를 이용하여 단순 체크를 하더라도 시간 안에 해결이 가능합니다.

 

#include <stdio.h>
int B, check = 0;

void recursion(int num, int count) {
    if(num == B) {
        printf("%d", count+1);
        check = 1;
    }
    if(num <= 500000000) recursion(num*2, count+1);
    if(num <= 100000000) recursion(num*10+1, count+1);
}

int main() {
    int A;
    scanf("%d %d", &A, &B);
    recursion(A, 0);
    if(!check) printf("-1");
}

 

B의 크기 제한은 최대 10억이므로, A가 연산을 통해 5억 이상이 되면 모든 연산이 불가해지며, 1억 이상이 되면 2를 곱하는 연산 외에는 가능한 것이 없습니다.

따라서 위와 같이 if문을 작성해주었고, 그 외에는 재귀적으로 계산해나가면서 수를 찾으면 연산 횟수를, 그렇지 않으면 check 변수에 기록이 되지 않아 -1을 출력하고 종료하는 방식으로 코드가 작동하게 되어있습니다.

 

 

계산을 진행해보면 실제로 수행 시간이 0ms로 연산이 거의 진행되지도 않고 모든 테스트케이스를 통과함을 확인할 수 있습니다.

알고리즘을 배웠다고 해서 무작정 사용하는 것이 좋은 방식은 아니라는 것을 깨달아 볼만한 문제라고 생각합니다.