[백준 / BOJ] 16953 A -> B

문제

출처 : www.acmicpc.net/problem/16953

16953번: A → B

정수 A와 B가 주어진다.

A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다.

이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다.

 

풀이

전형적인 BFS문제다.

BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다.

 

A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다.

예시로,

1. *2 연산은 32번만 반복해도 32억이라 최대범위를 벗어난다.(2^32)

2. *10 + 1 연산은 9번만 반복해도 최대범위를 벗어난다.

 

구현은

1. 현재 보고있는 수 == B 라면, cnt를 현재 cnt값으로 바꾸고 break 한다.

2. 현재 보고있는 수 > B 라면, 숫자가 더 작아지는 연산은 없으므로 바로 continue 한다.

3. 위 두가지 경우가 아니라면, 큐에 두가지 연산을 해준다.

q.push({현재 연산횟수 + 1, 현재 보고있는수 * 2});

q.push({현재 연산횟수 + 1, 현재보고있는수 * 10 + 1});

 

주의할점이 수의 범위는 최대 10억이지만, 99억...에서 *2를 하거나 *10+1을 할경우 int범위를 벗어날수있기때문에, long long으로 변수를 선언해줘야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/16953%20A%20-%3E%20B/main.cpp

devxb/JJUNalgo