이모티콘

📍 문제 설명

💡 접근

시간, 이모티콘의 갯수, 클립보드에 저장된 이모티콘 갯수를 저장해나간다.

방문처리를 할 때 현재 이모티콘 갯수와 클립보드의 갯수에 따라서 체크해줘야한다.

이미 처리된 부분이 나중에 계산된 부분한테 덮어씌워질 수 있다.

 

붙여넣기를 할 때 배열의 범위에 주의해야줘야 한다.

1.클립보드의 갯수가 n보다 크면 큐에 넣으면 안된다.

->계속 저장해서 클립보드에 저장하여 출력하는 경우 n인 부분에서 최솟값이 될거다.

2.1)과 마찬가지로 2000이 넘는 부분도 큐에 넣으면 안된다.

클립보드가 999일 때 이모티콘이 1000이면 그게 답이 될 수 있다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k, answer, cnt;
    static int[] arr, dis = {-1, 1, 2};
    static long[] dp;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Integer> q;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        //이모티콘 갯수와 클립보드에 따른 탐색 여부 담는 배열
        visited = new boolean[1001][1001];
        T.solution();

    }


    private void solution() {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(0, 1, 0));

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                Point cp = q.poll();
                if(cp.emoticon == n) {
                    System.out.println(cp.second);
                    return;
                }

                //1.화면에 있는 이모티콘 모두 복사해서 클립보드에 저장
                q.offer(new Point(cp.second+1, cp.emoticon, cp.emoticon));
                //2.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 -> 갯수 증가
                if(cp.clipBoard > 0 && cp.emoticon+cp.clipBoard <= n && !visited[cp.emoticon+cp.clipBoard][cp.clipBoard]) {
                    visited[cp.emoticon+cp.clipBoard][cp.clipBoard] = true;
                    q.offer(new Point(cp.second+1, cp.emoticon+cp.clipBoard, cp.clipBoard));
                }
                //3.화면이 있는 이모티콘 중 하나를 삭제 -> 갯수 감소
                if(cp.emoticon > 0 && !visited[cp.emoticon-1][cp.clipBoard]) {
                    visited[cp.emoticon-1][cp.clipBoard] = true;
                    q.offer(new Point(cp.second + 1, cp.emoticon - 1, cp.clipBoard));
                }
            }
        }
    }

    private static class Point {
        private int second;
        private int emoticon;
        private int clipBoard;


        public Point(int second, int emotion, int clipBoard) {
            this.second = second;
            this.emoticon = emotion;
            this.clipBoard = clipBoard;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "second=" + second +
                    ", emoticon=" + emoticon +
                    ", clipBoard=" + clipBoard +
                    "}";
        }
    }
}