[S2] A->B : 16953 : 그리디

문제

16953번: A → B

 

 

 

문제 접근

문제를 딱 읽었을 때 대체 어떻게 풀어야 하지..? 감이 안 잡히는 문제였다. 처음 수에서 마지막 수로 가는 규칙을 발견할 수 없었다.

그렇게 여러 고민을 해보다 마지막 수를 기준으로 돌아 가볼까! 생각했더니 쉽게 풀렸다.

 

 

 

알고리즘

B가 짝수라는 것은 직전 단계에서 X2 연산을 했다는 것이므로 나누기 2를 해준다.

B가 홀수라는 것은 직전 단계에서 마지막 자리에 1을 더했다는 것이므로 1를 빼고 10으로 나눈다. 

이 과정을 B가 A보다 클 때까지 반복한다.

A, B를 입력 받는다.

while( B가 A보다 클 때까지)
	if(B가 짝수) 
    	B를 2로 나눈다
    else (B가 홀수)
    	B에 -1를 하고 10으로 나눈다
    count++   
if(A==B) count 출력
else -1 출력

   

 

구현 코드

 알고리즘을 구현한 코드이다. 이 문제는 정답률이 30%대로 낮다. 그 원인은 바로 A가 1일 때 B로 만들수가 없는데도 -1을 출력하지 않기 때문이다. 예를 들어 A=1, B=15 일 떄 로직에 따라 B = (15-1)/10 = 1 이 된다. 테스트 케이스 1과 15의 케이스의 결과는 -1 이지만, 이때 A와 B는 같기 때문에 바로 while문을 빠져나가 count  값을 출력한다. 이 때문에 해당 케이스는 따로 처리하도록 하였다.

 public int solution(){
        int count = 1;
        while(B > A){
            if(B%2== 0){
                B /=2;
            }
            else{
                if(A == 1 && (B-1)/10 == 1){
                    if((B-1)%10 != 0)
                        return -1;
                }
                B = (B-1)/10;
            }
            count++;
        }
        if(A == B)
            return count;
        else
            return -1;
    }

 

 

---

전체 코드

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

public class Main {

    public static BufferedReader br;
    public int A;
    public int B;

    Main(){
        if(br == null){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
    }

    public void run() throws IOException {
        input();
        int result = solution();
        print(result);
    }


    public void input() throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
    }

    public int solution(){
        int count = 1;
        while(B > A){
            if(B%2== 0){
                B /=2;
            }
            else{
                if(A == 1 && (B-1)/10 == 1){
                    if((B-1)%10 != 0)
                        return -1;
                }
                B = (B-1)/10;
            }
            count++;
        }
        if(A == B)
            return count;
        else
            return -1;
    }

    public void print(int n){
        System.out.println(n);
    }

    public static void main(String [] args) throws IOException{
        new Main().run();
    }
}