[BOJ_14226] 이모티콘 (java)

문제링크

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

문제설명

문제

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

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

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

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

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

입력

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

출력

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

제한사항

제한시간	메모리제한
2초	512MB

출처 - www.acmicpc.net

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
BFS

이 문제는 정점을 어떻게 도출할지 굉장히 많이 고민하였습니다. 이모티콘의 개수를 정점으로 잡으면 클립보드에 들어있는 이모티콘의 수에 따라서 간선이 변경됩니다. 따라서 클립보드와 현재 이모티콘의 수로 간선을 만들어주어야 합니다. 즉 현재 이모티콘의 개수가 3개로 동일하더라도 클립보드에 3개, 5개 있는 경우를 다른 정점으로 보는 것 입니다. 이렇게 만드는 이유는 클립보드의 개수가 3개이면 연결되는 간선이 다음으로 6개로 5개이면 연결되는 간선은 8개로 이동되기 때문에 서로 다른 간선과 연결되어있다고 보아야하기 때문입니다.

 

따라서 저는 2차원으로 클립보드의 수, 현재 이모티콘 수로 문제를 해결하였습니다. BFS로 시간내에 해결할 수 있는지 확인하기 위해 정점의 개수를 확인해보면 2000 * 2000 하여 40만개가 있고 각 정점마다 간선이 3개씩 있으므로 120만이 됩니다. 이는 제한시간 2초내로 해결할 수 있으므로 적절한 알고리즘 방법이라고 생각하고 구현해 주었습니다.

 

 

구현코드

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

public class Main {
    public static void main(String[] args) {
        int count = new Scanner(System.in).nextInt();
        int[][] check = new int[1001][1001];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(0);
        check[1][0] = 1;

        while (!queue.isEmpty()){
            bfs(queue,check);
        }

        int min = check[count][1];
        for(int i = 1; i < check.length;i++){
            min = min > check[count][i] ? check[count][i] : min;
        }
        System.out.println(min-1);
    }

    public static void bfs(Queue<Integer> queue,int[][] check){
        int emoticonCount = queue.remove();
        int clipCount = queue.remove();

        if(emoticonCount-1 > 0 && check[emoticonCount-1][clipCount] == 0){
            queue.add(emoticonCount-1);
            queue.add(clipCount);
            check[emoticonCount-1][clipCount] = check[emoticonCount][clipCount] + 1;
        }
        if(check[emoticonCount][emoticonCount] == 0){
            queue.add(emoticonCount);
            queue.add(emoticonCount);
            check[emoticonCount][emoticonCount] = check[emoticonCount][clipCount] +1;
        }
        if(emoticonCount + clipCount < check.length&&check[emoticonCount + clipCount][clipCount] == 0){
            queue.add(emoticonCount+clipCount);
            queue.add(clipCount);
            check[emoticonCount+clipCount][clipCount] = check[emoticonCount][clipCount] +1;
        }
    }
}

 

시간복잡도

$O(V + E)$