문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

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

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

import java.io.*;
import java.util.*;
public class Main {
    static int S;
    static boolean[][] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        visited = new boolean[2001][2001];
        BFS();

    }
    public static void BFS() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0, 0));
        while (!q.isEmpty()) {
            Node n = q.poll();
            int window = n.window;
            int clip = n.clip;
            int cnt = n.cnt;
            if (window == S) {
                System.out.println(cnt);
                return;
            }
            if (window > 0 && window < 2000) {
                if (!visited[window][window]) {
                    visited[window][window] = true;
                    q.add(new Node(window, window, cnt+1));
                }
                if (!visited[window-1][clip]) {
                    visited[window-1][clip] = true;
                    q.add(new Node(window-1, clip, cnt+1));
                }
            }
            if (clip > 0 && window + clip < 2000) {
                if (!visited[window+clip][clip]) {
                    visited[window+clip][clip] = true;
                    q.add(new Node(window+clip, clip, cnt+1));
                }
            }
        }

    }
}
class Node {
    int window, clip, cnt;
    Node (int window, int clip, int cnt) {
        this.window = window;
        this.clip = clip;
        this.cnt = cnt;
    }
}

• Node 클래스에 화면에 이모티콘 개수, 클립보드에 개수, 시간 카운팅을 지정한다.
• 클립보드에 저장, 화면에 이모티콘 삭제, 화면에 클립보드 붙여넣기 순으로 로직 구성.
• 방문처리를 두 칸(visited[][])으로 나누어서 각각 할당할 수 있게 지정.
• 지문만 파악하면 단순하게 풀 수 있는 문제.
• visited를 2000으로 한 이유는 클립과 화면 이모티콘 합이 2000을 넘지는 않기 때문.