[알고리즘] BOJ 16953번 - A → B(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50

 

탐색

12 / 50(NEW!)

 

기초 동적 프로그래밍

9 / 50

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

16953번: A → B

→ solved.ac 기준 실버 2

---

문제 해결 아이디어

A에서 B로 바꾸되, 연산의 최솟값이므로 BFS를 이용하여 탐색

→ 처음 시도: 평소 풀던 것처럼 0에서 B까지 graph를 초기화하고, 방문 ⇒ 메모리 초과 발생

→ a에서 b로 가는데 안 가는 곳이 더 많을 것. python의 딕셔너리를 사용해서 visited를 확인하자.

---

구현

내 풀이(BFS)

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
  queue = deque()
  queue.append(a)
  while queue:
    x = queue.popleft()

    for nx in [x * 2, int(str(x) + '1')]:
      if nx < a or nx > b or graph.get(nx, -1) != -1:
        continue
      graph[nx] = graph[x] + 1
      queue.append(nx)

  if graph.get(b, -1) != -1:
    return graph[b] + 1
  return -1
  
a, b = map(int, input().split())
graph = dict()
graph[a] = 0

print(bfs())

 

다른 사람 풀이(Greedy)

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

answer = 1

while True:
  if a == b:
    break
  elif a > b:
    answer = -1
    break
  elif b % 10 == 1:
    b //= 10 # 1을 수의 가장 오른쪽에 추가한다. => 나머지가 1인지 확인한다.
    answer += 1
  elif b % 2 == 0:
    b //= 2 # 2를 곱한다 -> b를 2로 나눈다.
    answer += 1
  else:
    answer = -1
    break

print(answer)

 

• a를 b로 만드는 것이 아닌 b를 a로 만드는 형태의 풀이.
• 코드를 참고하면서 while 문의 조건을 a == b or answer == -1 이런식으로 바꿨는데 시간초과가 나서 if문을 그대로 쓸 수 밖에 없더라.. 

---

메모

• 걸린 시간: 20분
• python의 딕셔너리
  • d.get(k) : key에 다른 vaue 확인 시 시간 복잡도는 O(1)
  • d.get('a', False)
    • 딕셔너리 d의 key에 a가 있으면 해당 value를 반환
    • 그게 아니라면 뒤의 값(False)를 출력
• BFS로 풀었다면 메모리 초과에서, Greedy 였다면 시간 초과를 해결해야 하는 문제일 듯?

---