[백준|파이썬] 25418: 정수 a를 k로 만들기 (실버3)

문제

https://www.acmicpc.net/problem/25418

25418번: 정수 a를 k로 만들기

 

 

🐍파이썬

시간초과 코드 👉 BFS를 사용한 풀이

import sys
from collections import deque

a, k = map(int, sys.stdin.readline().split())

def bfs(answer, a):
  queue = deque()
  queue.append((answer, a))
  while queue:
    if a == k:
      return answer
    answer, a = queue.popleft()
    queue.append((answer+1, a+1))
    queue.append((answer+1, a*2))
    
print(bfs(0, a))

import sys

a, k = map(int, sys.stdin.readline().split())
answer = 0

while k > 0:	#k가 양수인 동안에만 반복
    if a == k:	#a == k인 경우
        print(answer)	#연산횟수를 출력 후 종료
        break
    else:	#a != k
        if k // 2 >= a:	#k//2가 a보다 크거나 같을 때
            if k % 2 == 0:	#k가 2의 배수이면
                k = k // 2	#k를 2로 나눈다
            else:	#k가 2의 배수가 아니면
                k -= 1	#k에서 1을 뺀다
        elif k - 1 >= a:	#k//2가 a보다 작아진 경우 해당 코드 실행
            k -= 1	#k에서 1을 뺀다
    answer += 1	#각 과정이 끝날 때마다 연산횟수+1

BFS 분류에 들어가 있는 문제이기도 했고 이전에 이 비슷한 문제를 BFS로 접근했던 적이 있어서(

[프로그래머스] 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS))

) BFS로 풀어보았는데 시간초과가 떴다...

이후 그리디 동전 나누기 문제를 떠올리고 k//2가 a보다 크거나 같은 경우 먼저 2로 나눈 뒤에 2로 나누어 떨어지지 않는 수만 -1 처리했고 k//2가 a보다 작은 경우 k-1이 a과 같아질 때까지 k에 -1 처리를 진행했다. 각 과정에서 answer에 +1을 하여 최종 연산횟수를 구했다. 

 

 

다른 풀이 방법

from sys import stdin

a,k = map(int,stdin.readline().split())
answer = 0

while k != a:	#k == a가 되면 반복문 종료
    if k % 2 == 0:	#k가 2로 나누어 떨어진다면
        if k//2 < a:
            break       
        k = k//2	#k//2가 a보다 크거나 같은 경우에만 k//2 진행
    else:	#k가 2로 나누어 떨어지지 않는다면
        k -= 1    #k-1
    answer += 1	#연산횟수 체크
#위의 반복문에서 체크한 연산횟수 + k//2가 a보다 작은 경우 k와 a가 같아질 때까지 -1을 진행하는 횟수
print(answer + (k-a))