백준 16953 A → B 문제 풀이
백준 16953 A → B 문제 풀이
백준 온라인 저지, 16953번: A → B
도입
어떤 그리디 문제는 명시적인 그래프 표현이 없더라도 그래프 탐색 전략을 사용하여 해결할 수 있다.
사실 이상한 이야기는 아니다. 그래프 탐색도 반복 과정을 사용하는 다른 알고리즘과 마찬가지로, 목표를 달성하기 위해 반복 과정을 어떻게 사용할지, 다음 반복과 이번 반복에서의 상태가 어떻게 변화해야하는지 설정한다.
문제 풀이
BFS를 변형하여 적용한다. 이 문제에서 정수 $A$는 절대로 연산에 의해서 감소되지 않는다. 따라서 반복 과정 상에서 $A$에 연산을 적용하여도 $B$보다 작다면 계속해서 BFS 큐에 연산을 적용한 $A$를 삽입한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A: int
B: int
def compute(A: int, B: int) -> int:
q: deque[tuple[int, int]] # (현재 A 값, 연산 횟수)
...
while q:
current, operated_count = q.popleft()
if current == B:
return operated_count
if current * 2 < B:
q.append((current * 2, operated_count + 1))
if current * 10 + 1 < B:
q.append((current * 10 + 1, operated_count + 1))
return -1
만약 큐가 빌 때 까지 if current == B: return operated_count에 의해 결과값이 반환되지 않는다면 주어진 연산을 사용하여 $A$로부터 $B$를 만드는 것은 불가능하다. 어떤 방법을 시도해도 $A$에 연산을 적용한 $A’$는 $B$를 초과하게 되고, 초과한 $A’$은 $B$로 축소시킬 수 없다.