문제 유형
: 처음에는 BFS를 써야겠다는 생각조차 하지 못했지만 BFS로 간단하게 풀 수 있는 문제
문제 해석
: 일단 문제에서 요구하는 것은 특정 수 N을 주어진 조건의 이상한 계산기로 만들기 위해서 몇번의 버튼을 눌러야하는지를 구하는 것이다. 이 때, 계산기에서 할 수 있는 선택지는 *2 와 //3 이다. 이러한 두개의 선택지만 가지고 N을 만들어야하는데, 이 때, 시작 값은 1부터 시작한다. 문제에서는 만들 수 없는 값은 입력값으로 주지 않지만, 만약에 N을 만들기 위해 5자리를 넘어서는 숫자를 사용하려하면 계산기가 고장나기 때문에 이 부분에 대해서 처리를 해줘야한다.
문제 풀이
: 사실 이문제에서 느낌이 와야하는 부분은 선택지가 2개이고, 그 선택지를 바탕으로 또다른 선택을 해나가는 방식이라는 것이다.
1
*2 //3
= 2 = 0
*2 //3 *2 //3
=4 = 0 =0 =0
: 위와 같은 방식으로 root node를 1로하면서 계속해서 2^n개의 규칙을 가지면서 늘어나는 이진트리가 된다. 선택지는 계속해서 하나의 선택지당 2개의 선택지이기 때문에 가능한 트리 모형이다. 그래서 이문제의 포인트는 계산기의 결과값에 2개의 선택지(*2, //3)가 있고, 그 선택지를 그래프 형태로 떠올릴 수 있어야 한다는 것 같다. 그러면 그 선택지로 나올 수 있는 모든 경우의수를 탐색할 수 있고(BFS든 DFS든), 그 중에 BFS를 통해 서치하는 것이 가장 효율적인 방법이므로 BFS를 선택해서 문제를 풀 수 있어야하겠다. 문제의 탐색 공간을 생각하면 모든 선택지를 고려해봐야하는데, 나는 그걸 처음에 단순 while문을 통해서 접근하려했다. 하지만, 그래프라는 자료구조를 떠올리는 순간 문제는 너무나도 쉬워진다. 아직까지 명확하지는 않지만, 이런식으로 문제에서 요구하는 로직을 자료구조의 특성에 매치시키면 문제를 푸는게 더욱 쉬워진다는 사실을 생각하고 넘어가자.
구현
depth = {}
path = {}
n = int(input())
if n == 1:
print(0)
else:
path[1] = True
depth[1] = 0
queue = [1]
def get_two_choices(num) :
return [num*2, num//3]
flag = False
while not flag:
top = queue.pop(0)
for el in get_two_choices(top):
try:
if path[el]:
continue
except:
if el == n:
flag = True
print(depth[top] + 1)
break
path[el] = True
if len(str(el)) > 5:
continue
depth[el] = depth[top] + 1
queue.append(el)
