백준 16953번 문제

그리디 알고리즘

문제

문제 해석

두가지의 연산을 활용하여 n -> m으로 도달하는 최단 거리를 계산 하는 문제.

코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_16953 {
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int cnt = 1;
        while(M!=N){
            if(M<N){
                cnt = -1;
                break;
            }
            if(M %10!=1 && M%2!=0 ) {
                cnt = -1;
                break;
            }

            if(M%2==0){
                M = M/2;
            }
            else if(M%10==1){
                M = (M-1)/10;
            }
            cnt++;
        }
        System.out.println(cnt);
    }
}

해결방법

1. m이 n보다 작은 경우 종료.
2. n에서 m으로 가는 것이 아니라 m에서 n으로 가는 방법을 채택.
3. m이 두 연산 모두 불가능한 경우 종료.
4. 두 연산중 하나가 해당하면 연산을 적용하고 cnt에 1 더하기.
5. 두 수가 같아지는 경우 종료 후 cnt를 출력.