작성 코드

import java.io.*;
import java.util.*;
public class emoticon_14226 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 화면, 클립보드
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        dp[1][0] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int now = current[0];
            int clip = current[1];

            // 목표 개수에 도달한 경우
            if (now == n) {
                System.out.println(dp[now][clip]);
                break;
            }

            // 화면에 있는 이모티콘을 복사해서 클립보드에 저장
            if (dp[now][now] == -1) {
                dp[now][now] = dp[now][clip] + 1;
                queue.add(new int[]{now, now});
            }

            // 클립보드에 있는 이모티콘을 화면에 붙여넣기
            if (now + clip <= n && dp[now + clip][clip] == -1) {
                dp[now + clip][clip] = dp[now][clip] + 1;
                queue.add(new int[]{now + clip, clip});
            }

            // 화면에 있는 이모티콘 중 하나를 삭제
            if (now - 1 >= 0 && dp[now - 1][clip] == -1) {
                dp[now - 1][clip] = dp[now][clip] + 1;
                queue.add(new int[]{now - 1, clip});
            }
        }
    }
}

설명

해당 코드는 BFS(Breadth-First Search) 알고리즘을 사용하여 이모티콘 생성 문제를 해결하는 코드입니다. 아래는 코드의 구성과 동작에 대한 설명입니다.

• 자료구조:

  • dp: 2차원 배열로서, dp[i][j]는 화면에 이모티콘이 i개 있고 클립보드에 이모티콘이 j개 있는 상태에서 이모티콘을 만들기 위해 필요한 최소 시간을 저장합니다. 초기값은 -1로 설정되어 있습니다.
  • queue: BFS 탐색을 위한 큐 자료구조로, 각 원소는 현재 상태를 나타내는 [now, clip]의 형태입니다.

• 로직:

  • 초기화: dp[1][0]를 0으로 초기화하고, 큐에 시작 상태인 [1, 0]를 추가합니다.
  • BFS 탐색: 큐가 빌 때까지 아래 과정을 반복합니다.
    • 큐에서 원소를 꺼내 현재 이모티콘 개수 now와 클립보드의 이모티콘 개수 clip을 얻습니다.
    • 현재 이모티콘 개수 now가 목표 개수인 n과 같으면, dp[now][clip] 값을 출력하고 탐색을 종료합니다.
    • 현재 상태에서 다음 상태로 전이하는 과정을 수행합니다.
      • 화면에 있는 이모티콘을 복사해서 클립보드에 저장: dp[now][now]가 -1인 경우에만 해당 상태를 큐에 추가하고, dp[now][now] 값을 갱신합니다.
      • 클립보드에 있는 이모티콘을 화면에 붙여넣기: now + clip <= n인 경우, dp[now + clip][clip]가 -1인 경우에만 해당 상태를 큐에 추가하고, dp[now + clip][clip] 값을 갱신합니다.
      • 화면에 있는 이모티콘 중 하나를 삭제: now - 1 >= 0인 경우, dp[now - 1][clip]가 -1인 경우에만 해당 상태를 큐에 추가하고, dp[now - 1][clip] 값을 갱신합니다.

• 결과 출력: BFS 탐색을 통해 목표 이모티콘 개수인 n을 만들기 위해 필요한 최소 시간인 dp[n][clip] 값을 출력합니다.

이렇게 BFS 알고리즘을 사용하여 모든 가능한 상태를 탐색하면서 최소 시간을 갱신하여 최적해를 찾습니다.

자바스크립트

function solve(n) {
  const dp = Array.from(Array(n + 1), () => Array(n + 1).fill(-1));
  const queue = [];
  queue.push([1, 0]);
  dp[1][0] = 0;

  while (queue.length > 0) {
    const [now, clip] = queue.shift();

    if (now === n) {
      return dp[now][clip];
    }

    if (dp[now][now] === -1) {
      dp[now][now] = dp[now][clip] + 1;
      queue.push([now, now]);
    }

    if (now + clip <= n && dp[now + clip][clip] === -1) {
      dp[now + clip][clip] = dp[now][clip] + 1;
      queue.push([now + clip, clip]);
    }

    if (now - 1 >= 0 && dp[now - 1][clip] === -1) {
      dp[now - 1][clip] = dp[now][clip] + 1;
      queue.push([now - 1, clip]);
    }
  }
}

// 백준에서 입력을 받는 코드
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    console.log(solve(parseInt(line)));
  })
  .on("close", () => {
    process.exit();
  });

파이썬

from collections import deque

def solve(n):
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    queue = deque()
    queue.append((1, 0))
    dp[1][0] = 0

    while queue:
        now, clip = queue.popleft()

        if now == n:
            return dp[now][clip]

        if dp[now][now] == -1:
            dp[now][now] = dp[now][clip] + 1
            queue.append((now, now))

        if now + clip <= n and dp[now + clip][clip] == -1:
            dp[now + clip][clip] = dp[now][clip] + 1
            queue.append((now + clip, clip))

        if now - 1 >= 0 and dp[now - 1][clip] == -1:
            dp[now - 1][clip] = dp[now][clip] + 1
            queue.append((now - 1, clip))

n = int(input())
result = solve(n)
print(result)