[백준 14226][Gold 4] - 이모티콘 (JAVA)

문제 링크

---

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

 

문제

---

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

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

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

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

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

 

입력

---

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

 

출력

---

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

 

문제 해석

---

영선이가 할 수 있는 행동은 크게 3가지 이다.

• 화면의 이모티콘을 클립보드에 저장
• 클립보드의 이모티콘을 화면의 이모티콘에 붙여넣기
• 화면의 이모티콘을 삭제

우리는 영선이가 위의 행동 중 1개를 반복했을 때 목표 길이인 S길이의 이모티콘을 나오게 하는 최소 횟수를 구하면 된다.

단순 구현으로 풀릴까?

---

우선 가장 쉬운 방법인 구현을 생각해보자. 선택할 수 있는 행동은 3개이므로 단순 조합으로 생각하면 3^N일 것이다. 이때 N은 최대 1000이므로 3^1000은 1억보다 크기 때문에 단순 조합으로는 해결할 수 없다.

하지만 최소 횟수를 구하는 것이기 때문에 이전에 만들어진 이모티콘이 또다시 만들어졌다면 해당 경우의 수는 이미 최소 횟수로 만들어진 이모티콘이 아니기 때문에 다시 경우의 수를 구할 필요가 없다. 그러므로 우리는 방문처리를 제대로 하면 시간복잡도를 단축시킬 수 있다.

 

방문처리 배열을 만들어 보자

---

방문 처리란 이미 탐색한 경우의 수를 저장해 해당 경우의 수가 등장한다면 무시하는 과정을 말한다. 그렇기 때문에 이 문제의 경우의 수는 무엇인지 이루어져 있는지 생각해보자.

이 문제에서 행동은 다시 말하면 3가지가 있다.

• 화면의 이모티콘을 클립보드에 저장
• 클립보드의 이모티콘을 화면의 이모티콘에 붙여넣기
• 화면의 이모티콘을 삭제

여기서 변화하는 값을 주목하면 다음과 같다.

• 화면의 이모티콘을 클립보드에 저장
• 클립보드의 이모티콘을 화면의 이모티콘에 붙여넣기
• 화면의 이모티콘을 삭제

 

변화하는 값은 화면의 이모티콘과 클립보드의 이모티콘이므로 2가지의 조합으로 경우의 수를 만들 수 있다. 이를 2차원 배열로 표현하면 다음과 같다. 

int[클립보드 이모티콘][화면 이모티콘] = (클립보드 이모티콘을 가지고 화면에 이모티콘을 띄었을 때 걸린 시간)

이때 우리는 모든 S길이의 화면의 이모티콘 중 최소 시간을 구해야하기 때문에 클립보드 별 이모티콘을 만드는 시간을 저장하기 위해 int형으로 방문배열을 만들었다.

우리는 한번 방문한 곳을 또다시 방문하면 뒤늦게 완성된 이모티콘이므로 무시할 예정이다. 그러므로 시간복잡도는 배열의 크기와 같아 S*S = S^2 이며 최대 연산 횟수는 1000*1000 = 1,000,000 으로  제한시간 2초의 예상 연산 횟수인 2억보다 작아 주어진 시간내로 문제를 해결할 수 있다!

 

코드

---

mport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    final static int INF = Integer.MAX_VALUE;

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

        int[][] time = new int[S+1][S+1];

        for(int i=0;i<=S;i++){
            Arrays.fill(time[i],INF);
        }

        time[0][1] = 0;

        PriorityQueue<Imoj> q = new PriorityQueue<>();
        q.add(new Imoj(0,1,0));

        while(!q.isEmpty()){
            Imoj imoj = q.poll();
            if(time[imoj.clipBoard][imoj.length] < imoj.time){
                continue;
            }
            if(imoj.length == S){
                System.out.println(imoj.time);
                break;
            }

            //삭제한 경우
            if(imoj.length - 1 > 0 && time[imoj.clipBoard][imoj.length-1] > imoj.time + 1){
                Imoj next = new Imoj(imoj.time+1, imoj.length - 1, imoj.clipBoard);
                time[imoj.clipBoard][next.length] = next.time;
                q.add(next);
            }

            //기존 클립보드 사용한 경우
            if(imoj.clipBoard != 0 && imoj.length + imoj.clipBoard <=S
                    && time[imoj.clipBoard][imoj.length + imoj.clipBoard] > imoj.time + 1){
                Imoj next = new Imoj(imoj.time + 1, imoj.length + imoj.clipBoard,imoj.clipBoard);
                time[imoj.clipBoard][next.length] = next.time;
                q.add(next);
            }

            //복사하는 경우
            if(time[imoj.length][imoj.length] > imoj.time+1){
                Imoj next = new Imoj(imoj.time+1, imoj.length,imoj.length);
                time[next.clipBoard][next.length] = next.time;
                q.add(next);
            }

        }
    }
}
class Imoj implements Comparable<Imoj>{
    int time;
    int length;
    int clipBoard;
    
    public Imoj(int time, int length,int clipBoard){
        this.time = time;
        this.length = length;
        this.clipBoard = clipBoard;
    }

	//이모티콘이 완성된 시간을 기준으로 오름차순 정렬
    @Override
    public int compareTo(Imoj o) {
        return this.time - o.time;
    }
}

 

 

실행 결과

---

 

 

제한시간인 2초안에 문제가 해결되었다!

 

 

키워드

---

• 최소 횟수
  
  • DP, 완전탐색, 그리디의 가능성을 가지고 있다.

 

팁

---

시간마다 변화하는 것이 곧 경우의 수가 되므로 해당 조건들을 이용해 방문처리를 하자.