320x100
16953번 : A → B
이전에 이 문제와 비슷한 문제를 푼 적이 있었는데, 그 문제가 더 어려웠던 것 같다. 이 문제는 일단 수가 무조건 증가하기 떄문에 해당 수를 넘기면 그 수에 대해서는 검사하지 않아도 된다.
내 코드:
# dawitblog.tistory.com
from collections import deque
a,b = map(int,input().split())
queue = deque([(a,0)])
while queue:
temp,count = queue.popleft()
n = temp * 2
m = temp * 10 + 1
if n == b or m == b:
print(count+2)
exit()
if n < b:
queue.append((n,count+1))
if m < b:
queue.append((m,count+1))
print(-1)
bfs를 통해 간단하게 구현할 수 있다. 그런데 사실 이 문제는 bfs를 사용하지 않아도 된다...
skyhp님의 코드:
n,m = map(int,input().split())
count=0
while n!=m:
if n>m:
count=-2
break
elif str(m)[-1]=='1':
m=m//10
count+=1
elif m%2==0:
m=m//2
count+=1
else:
count=-2
break
print(count+1)
그냥 m에서 거꾸로 내려오는 방식을 사용해도 된다!!
'PS > solved.ac' 카테고리의 다른 글
[CLASS 4]백준 1916번 - 최소비용 구하기 (0) | 2021.03.21 |
---|---|
[CLASS 4]백준 1753번 - 최단경로 (0) | 2021.03.16 |
[CLASS 4]백준 11660번 - 구간 합 구하기 5 (0) | 2021.03.14 |
[CLASS 4]백준 5639번 - 이진 검색 트리 (0) | 2021.03.12 |
[CLASS 4]백준 1991번 - 트리 순회 (0) | 2021.03.09 |
댓글