[백준/Java] 25418번 정수 a를 k로 만들기

✏️ 문제 탐색

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

 

정수 A에 1을 더한다.

정수 A에 2를 곱한다.

두 연산을 이용하여 A를 K로 변경할 때, 최소 연산 횟수를 구하는 문제이다.

✏️ 구현 아이디어

모든 경우를 완전 탐색으로 찾는 경우 시간 복잡도는 O(2^N)이다.

A와 K가 최대 1,000,000이므로 최대 연산은 2^1,000,000

2^10=약 1,000이므로 2^1,000,000은 제한 시간(1초) 안에 연산할 수 없다.

 

A가 K가 될 수 있는지 판단하려면 1을 더하고 2를 곱하면서 모든 경우를 찾는 수밖에 없다.

하지만 반대로 K에서 1을 빼고 2를 나누면서 A가 될 수 있는지 판단한다면 불필요한 경로를 배제할 수 있다.

 

예를 들어 7이 77이 될 수 있는지 판단한다면 7에서 +1, *2 두 가지 연산을 하고

그 결과 각각마다 또 +1, *2 두 가지 연산을 하는 행위를 반복해야 한다.

 

하지만 반대로 77이 7이 될 수 있는지 판단한다면 77에서 -1, /2 두 가지 연산을 할 것이다.

이 때 77/2는 정수로 떨어지지 않는다. 즉 7에서 77이 되기 위해 이 경로를 거치지 않았다는 의미이다.

따라서 이 탐색경로는 연산에서 배제시킬 수 있다.

✏️ 알고리즘

백트래킹

✏️ 시간 복잡도

현재 탐색 중인 숫자가 홀수일 때마다 탐색 횟수가 반씩 줄어들기 때문에 O(K/2 + logK/2)가 아닐까 예상해봄..

✏️ 오답 노트

백트래킹 조건으로 if(K<A) return;을 빠트림

✏️ 코드 설계

1. A, K 입력 받기
2. K에서 -1, /2연산을 백트래킹으로 수행
   1. 이미 K=A인 경우를 찾았거나, K가 A보다 작아진 경우 더 이상 수행할 필요 없으므로 재귀 탐색 종료
   2. K=A이면 연산을 몇 번 수행했는지 저장하고 탐색 종료
   3. K값이 0 이하이면 더 이상 수행할 필요 없으므로 탐색 종료
   4. K가 2의 배수일 때만 2로 나눈 값을 재귀호출
   5. 그 외의 경우 모두 1 뺀 값을 재귀호출
3. A를 가장 먼저 찾는 경우, 백트래킹 종료하고 연산 횟수를 출력

✏️ 정답 코드

import java.io.*;
import java.util.*;

public class Main{
    static int A, K, ans, totalcnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        recursive(K, 0);
        System.out.println(ans);

    }
    static void recursive(int K, int cnt){
        if(ans != 0 || K<A) return;
        if(K == A){
            ans = cnt;
            return;
        }
        if(K <= 0) return;
        if(K%2 != 0) recursive(K-1, cnt+1);
        else recursive(K/2, cnt+1);
        recursive(K-1, cnt+1);

    }

}

✏️ Note

• 사실 이 풀이 방법이 맞는지 긴가민가했다. 시간 복잡도를 정확하게 계산하지 못한 상태에서 풀었기 때문에..
• 비슷한 문제를 예전에도 풀어본 적이 있어서 백트래킹을 떠올릴 수 있었다.
• 조건을 빠트려서 중간에 시간 초과가 한 번 나긴 했지만 유형과 풀이 방법을 빨리 떠올릴 수 있었던 문제이다.