👨‍💻 문제

---

✍️ 풀이

⚗️ 해석

문제에 쓰여있는 연산은 아래와 같다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

해당 연산을 해석하면 이러하다.

1. 클립보드 = 화면
2. 화면 = 화면 + 클립보드
3. 화면 = 화면 - 1

📈 2차원 배열

행과 열이 화면에 표현된 이모티콘의 수와 클립보드에 저장된 이모티콘의 수를 의미하는 배열을 만든다.

화면에 표현된 이모티콘의 수가 1개이고,
클립보드에 저장된 이모티콘의 수가 0개라면,
표에 해당하는 좌표는 (1, 0)이 된다.

배열의 값은 소모된 시간을 의미한다.

초기 상태인 (1, 0)은 0으로 초기화해준다.

📈 DP & BFS

1. 클립보드 = 화면
2. 화면 = 화면 + 클립보드
3. 화면 = 화면 - 1

위 연산들대로 표를 채워나가면 아래와 같은 형태로 채워지게 된다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {

    private static final int INF = Integer.MAX_VALUE;
    private static final int MAX_N = 1000;

    private static int N;
    private static int[][] times; // [screen][clipboard]

    private static class Coordinate {

        int screen;
        int clipboard;

        public Coordinate(int screen, int clipboard) {
            this.screen = screen;
            this.clipboard = clipboard;
        }
    }

    private static Queue<Coordinate> q = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
        times = new int[MAX_N + 1][MAX_N + 1];
        for (int i = 0; i <= MAX_N; i++) {
            Arrays.fill(times[i], INF);
        }
        times[1][0] = 0;
        q.add(new Coordinate(1, 0));

        while (!q.isEmpty()) {

//            for (int i = 0; i <= MAX_N; i++) {
//                System.out.println(Arrays.toString(times[i]));
//            }

            Coordinate coordinate = q.poll();

            int time = times[coordinate.screen][coordinate.clipboard];

            if (coordinate.screen == N) {
                System.out.println(time);
                return;
            }

            // 1. clipboard = screen
            replaceValueAndAddQueueIfFaster(time + 1, coordinate.screen, coordinate.screen);

            // 2. screen += clipboard
            replaceValueAndAddQueueIfFaster(time + 1, coordinate.screen + coordinate.clipboard, coordinate.clipboard);

            // 3. screen--
            replaceValueAndAddQueueIfFaster(time + 1, coordinate.screen - 1, coordinate.clipboard);
        }
    }

    private static void replaceValueAndAddQueueIfFaster(int time, int screen, int clipboard) {
        if (screen < 0 || screen > MAX_N) {
            return;
        }
        if (time < times[screen][clipboard]) {
            times[screen][clipboard] = time;
            q.add(new Coordinate(screen, clipboard));
        }
    }

}

🔍️ 참고

N의 값에 상관없이 N의 최댓값인 1000으로 배열의 크기를 초기화하고 있다.
이는 1000개의 경우 화면에 500개가 있을 때, 클립보드 복붙으로 가장 빠르게 1000개를 완성할 수 있지만,
999개의 경우, 1000개에서 1개를 빼야 가장 빠를 것이라고 생각된다.
이러한 경우를 생각하면 N에 딱 맞게 배열을 만들게 되면 정확한 결과를 얻을 수 없을 수도 있다.

또한 배열의 값들은 N의 값에 관계없이 일정하다.
그렇지만 N을 완성했음에도 불필요하게 배열을 계속 채울 수 있다.
그러한 연산을 방지하기 위해 아래 조건문을 통해 반복을 끝내버린다.

            if (coordinate.screen == N) {
                System.out.println(time);
                return;
            }

replaceValueAndAddQueueIfFaster() 메소드의 조건문
if (time < times[screen][clipboard]) 는 이미 방문한 위치를 다시 큐에 넣지 않기 위함이다.
모든 배열의 값을 INF (Integer.MAX_VALUE)로 초기화했기에 해당 조건문은 if (time != INF)로 대체할 수 있다.