[Java] BaekJoon 14226. 이모티콘 (BFS) (골드5)

문제출처: https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

문제이해

 

목표

다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. (2 <= S <= 1000)

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

모든 연산은 1초가 걸린다. 
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성

 

풀이

DP 문제로 이해 => X 틀림

DP로만 풀게 되면 3번 조건(이모티콘 중 하나 삭제)으로 구할 수 있는 최소값 경우의 수를 고려하지 못함 or 고려하더라도 너무 많은 경우를 탐색해야되서 초과

=> DP와 BFS로 풀이 (탐색 우선 순위는 해당 이모티콘을 출력하기까지 Price(시간)가 낮은 순서대로) 

min[]: 최소 걸리는 시간을 다루는 배열
        인덱스: i개의 이모티콘,
        값: i개의 이모티콘을 만드는데 걸리는 시간의 최솟값

1. 증식 방법 

- 자기보다 1 적은 이모티콘으로 탐색 -> min[현재 - 1] + 1
- 자기 * j (j: 2~) 배수의 이모티콘으로 탐색 -> min[현재 * j] + j

2. 증식과 함께 갱신

증식: 큐에 넣어서 BFS 탐색을 한다.
갱신: 가능한 적은 price비용으로 min[]의 값을 갱신한다.  

 

주의 

min[]의 초기화: => min[i] = i 

- 1을 복사에서 i번씩 복붙하는 경우가 시간의 최댓값 이므로 인덱스 값으로 초기화

- 의미: 위의 증식방법 2가지로 했을 때 도달하지 못할 수 있는 소수값을 미리 의미있는 최대값으로 초기화 시켜서 잘못된 정답이 도출될 수 있는 것을 방지

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

/*
   낮은 cost(시간)로 먼저 BFS 탐색하는 알고리즘
   증식 방법->
     - 자기보다 1 적은 이모티콘으로 탐색 -> min[현재 - 1] + 1
     - 자기 * j 배수의 이모티콘으로 탐색 -> min[현재 * j] + j
   */

public class 이모티콘 {

    final static int PRICEMAX = 1000;
    final static int INDEXMAX = 1010;

    private static int[] min;
    private static int N;

    static class Emoticon {
        int index;
        int price;

        public Emoticon(int index, int price) {
            this.index = index;
            this.price = price;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 최소 걸리는 시간을 다루는 배열(인덱스: i개의 이모티콘, 값: i개의 이모티콘을 만드는데 걸리는 시간의 최솟값)
        min = new int[INDEXMAX];
        for (int i = 1; i < INDEXMAX; i++) { // 1을 복사에서 i번씩 복붙할 수 있음으로 인데그 값으로 초기화
            min[i] = i;
        }

        // BFS를 탐색할 PriorityQueue 생성
        PriorityQueue<Emoticon> pq = new PriorityQueue<Emoticon>((a, b) -> {
            return a.price - b.price;
        });
        pq.add(new Emoticon(2, 2));
        pq.add(new Emoticon(3, 3));

        // BFS
        while (!pq.isEmpty()) {
            Emoticon emoticon = pq.poll();
            int index = emoticon.index;
            int price = emoticon.price;
            if (index == N) {
                break;
            }
            if (index <= 0 || index >= INDEXMAX - 1 || price > min[index]) {
                continue;
            }

            // 이모티콘 - 1 한 값에 접근
            if (min[index - 1] >= price + 1) {
                min[index - 1] = price + 1;
                pq.add(new Emoticon(index - 1, min[index - 1]));
            }

            // 이모티콘 * j (배수) 값에 접근
            for (int j = 2; j < INDEXMAX; j++) {
                int multipleIndex = index * j; // 배수
                if (multipleIndex >= INDEXMAX) {
                    break;
                }
                if (min[multipleIndex] >= price + j) {
                    min[multipleIndex] = price + j;
                    pq.add(new Emoticon(multipleIndex, min[multipleIndex]));
                }
            }
        }

        System.out.println(min[N]);
    }

}