21.08.07 - [BOJ] 14226. 이모티콘

[suhyunsim]

문제

• 14226

핵심 아이디어

s: 화면, c: 클립보드

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

• (s, c) -> (s, s)

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

• (s, c) -> (s + c, s)

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

• (s, c) -> (s - 1, c)
• dist[s, c]:
  • dist가 -1: 방문안함
  • 0이상이면: 방문했고 그 때 걸리는 최소시간

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q14226;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] d = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(d[i], -1);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); //s 초기값
        queue.add(0); //c 초기값
        d[1][0] = 0;
        while (!queue.isEmpty()) {
            int s = queue.remove();
            int c = queue.remove();
            if (d[s][s] == -1) { //방문 안했으면?
                d[s][s] = d[s][c] + 1;
                queue.add(s);
                queue.add(s);
            }
            if (s + c <= n && d[s + c][c] == -1) {
                d[s + c][c] = d[s][c] + 1;
                queue.add(s + c);
                queue.add(c);
            }
            if (s - 1 >= 0 && d[s - 1][c] == -1) {
                d[s - 1][c] = d[s][c] + 1;
                queue.add(s - 1);
                queue.add(c);
            }
        }
        int ans = -1;
        for (int i = 0; i <= n; i++) {
            if (d[n][i] != -1) {
                if (ans == -1 || ans > d[n][i]) {
                    ans = d[n][i];
                }
            }
        }
        System.out.println(ans);
    }
}