백준-25418번(정수 a를 k로 만들기)-pyhton3

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

제한

1 ≤ A < K ≤ 1,000,000

예제 입력 1

5 10

예제 출력 1

1

5(A), 10(연산 2)가 최소 연산이므로 정답은 1이다.

예제 입력 2

7 77

예제 출력 2 

7

7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다.

예제 입력 3

1111 997651

예제 출력 3

850

---

나의 코드

파이썬

from collections import deque
A,K=map(int,input().split())
kl=[0 for i in range(K+1)]

dq=deque([(A+1,1),(A*2,1)])

while dq:
    x,y=dq.popleft()
    if(x==K):
        print(y)
        break
    if(x+1<=K and not kl[x+1]):
        dq.append((x+1,y+1))
        kl[x+1]=1
        if(x+1==K):
            print(y+1)
            break
    if(x*2<=K and not kl[x*2]):
        dq.append((x*2,y+1))
        kl[x*2]=1
        if(x*2==K):
            print(y+1)
            break

 

자바

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

class data{
    int a;
    int b;
}
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int A=sc.nextInt();
        int K=sc.nextInt();
        Deque<data> deque=new ArrayDeque<data>();
        int[] arr=new int[K+1];
        data dd=new data();
        arr[A]=1;
        dd.a=A;
        dd.b=0;
        deque.add(dd);
        while(!(deque.isEmpty())){
            data x=deque.removeFirst();
            if(x.a==K){
                System.out.println(x.b);
                break;
            }
            if(x.a+1<=K && arr[x.a+1]!=1){
                data d=new data();
                d.a=x.a+1;
                d.b=x.b+1;
                arr[x.a+1]=1;
                deque.add(d);
            }
            if(x.a*2<=K && arr[x.a*2]!=1){
                data d=new data();
                d.a=x.a*2;
                d.b=x.b+1;
                arr[x.a*2]=1;
                deque.add(d);

            }


        }
    }

}