문제 탐색하기

입력 자료 정리

1. 입력값 a는 탐색의 시작값이며, k는 탐색의 목표값이다.

해결방법 추론

1. 두 연산에 대한 모든 경우를 구해야하므로 BFS/DFS가 후보가 될 것이다
2. 하지만 DFS를 선택할 수는 없다. K의 최대가 100만이기 때문이다.
3. 메모리 초과가 발생할 것이므로 BFS 탐색을 선택하여 해결하는 것을 생각했다
4. 연산 수를 관리하는 배열을 두지만 구분은 지어줘야한다. 단순 덧셈이 아니기 때문이다
5. 배열의 첫번째 인덱스 값을 선택할 때는 합하고, 두번째를 선택할 때는 곱하도록 한다
6. 탐색하면서 큐에는 현재 위치의 값과 누적된 연산 횟수를 배열로 갖도록 하며,
   방문배열을 통해 중복 탐색을 하지 않도록 한다
7. 연산결과 나온 수를 선택하는 경우는 목표인 target 수보다 작거나 같으면서
   미방문한 배열에 대해서만 진행한다
8. 7번 조건으로 탐색의 한도를 두었기 때문에 무한 탐색을 방지할 수 있다
9. 탐색 도중 큐의 첫번째 인덱스의 값이 target과 같으면 ans를 최소값으로 갱신한다

시간복잡도 계산

1. k의 최대값인 100만이 최대 연산이 된다. 예를 들어 1에서 100만을 목표로 할 때,
   1만 100만번 더하는 경우가 최악으로 될 수 있기 때문이다
2. 따라서 시간복잡도는 O(k)가 되며, 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. 입력값들은 a와 k라는 이름을 가진 int형 변수로 보관한다
2. 방문 배열은 최대 탐색범위인 100만 인덱스 까지 갖도록 1,000,001만큼의 크기를 갖도록 한다
3. 정답 출력을 위한 int형 변수 ans를 선언한다.
   이때 최소값을 갖도록 하기 위해 Integer.MAX_VALUE로 초기화한다

BFS 탐색 설계

1. int형 1차원 배열을 타입으로 가지는 큐를 선언하고 BFS 탐색을 진행한다
2. 언제나 그랬듯이 시작지점과 누적 연산 횟수인 0을 넣어주고 방문체크후 탐색을 시작한다
3. BFS 탐색에서 target을 발견하는 순간 ans에 최소값을 비교하여 넣어준다
4. 연산횟수만큼 탐색하면서 0일때는 합, 1일때는 곱을 진행한다
5. 범위를 벗어나지 않으며 미방문한 수만 큐에 넣어준다

출력값 설계

1. 완성한 ans를 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공!)

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


public class Main {

    static int[] dx = {1, 2};
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;
    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());
        int a = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        visited = new boolean[1000001];
        bfs(a, k);

        bw.write(ans+"");
        
        br.close();
        bw.close();
    }

    private static void bfs(int start, int target) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});
        visited[start] = true;
        while(!q.isEmpty()) {
            int[] now = q.poll();

            if(now[0] == target){
                ans = Math.min(ans, now[1]);
            }


            for (int i = 0; i < 2; i++) {
                if(i == 0){
                    int nx = now[0] + dx[i];
                    if(nx <= target && !visited[nx]){
                        visited[nx] = true;
                        q.add(new int[]{nx, now[1] + 1});
                    }
                }else{
                    int nx = now[0] * dx[i];
                    if(nx <= target && !visited[nx]){
                        visited[nx] = true;
                        q.add(new int[]{nx, now[1] + 1});
                    }
                }
            }

        }

    }
}

문제 링크

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