[백준 1700][Gold 1] - 멀티탭 스케줄링(JAVA)

문제 링크

---

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

 

문제

---

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

 

입력

---

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

 

출력

---

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

 

문제 해석

---

멀티탭에 플러그를 꽂는 행동은 크게 3가지이다.

• 멀티탭에 사용하려고 하는 가전제품의 플러그가 꽂혀있는 경우
  • 그대로 사용한다.
• 멀티탭에 꽂을 자리가 있는경우
  • 빈자리에 꽂는다.
• 멀티탭에 꽂을 자리가 없는 경우
  • 꽂혀있는 것 중 1개를 뽑는다.

 

위의 조건 중에서 분기가 갈리는 부분은 바로 멀티탭에 꽂을 자리가 없는 경우이다. 우리는 플러그를 빼는 최소의 횟수를 구해야 하므로 어떤 플러그를 뽑아야 할지 고민해야한다.

단순 구현으로 풀릴까?

---

우선 가장 쉬운 방법인 구현을 생각해보자. 최대 멀티탭 구멍의 개수는 100개 이므로 선택할 구멍도 100개이다. 또한 새롭게 들어오는 전기 용품도 100개 이므로 이를 시간 복잡도로 표현하면 다음과 같다.

 O(n)
= (선택할 구멍의 개수) ^ (전기용품 개수)
= n^n

최대 n의 크기는 100이기 때문에 구현으로 풀었을 때 걸리는 최대 예상 시간은 100^100 = 1.e+200이다. 지수 표기법으로 값이 나온 것을 봐서 1초는 커녕 1분이 걸려도 안될 것 같다. 우리는 다른 방법을 찾아야 한다. 최소의 경우의 수를 찾는 방법은 dp와 그리디가 있다. 

 

dp로 해결해볼까??

---

dp로 해결하기 위해선 점화식을 만들어야 한다. 점화식으로 풀겠다는 것은 Top-Down이던 Bottom-Up이던 순차적으로 경우의수를 찾을 수 있어야한다. 하지만 위의 문제는 뒤에 새롭게 나올 가전제품이 현재 멀티탭에 꽂혀있냐 않냐에 따라 경우의 수가 바뀔 수 있다. 즉 n번 구멍에 k번 가전제품에 있음에 따라 경우의 수를 다 구해야하니 이를 배열로 표현하면 dp[현재 순서][n번째 구멍][가전제품 종류]으로 표현되는거 같은데.....................

........... 하지만 아무리 생각해도 규칙을 찾을 수 없어 이이상 점화식으로 표현될 방법이 생각나지 않는다. 나머지 남은 방법인 그리디로 생각해보자.

 

그리디로 해결해볼까??

---

그리디로 해결하기 위해 이득이 되는 경우와 손해를 보는 경우를 생각해보자.

 

1. 가장 큰 이득이 되는 것

가장 이득을 보려면 앞으로 생기는 가전제품이 이미 멀티탭에 있어서 플러그를 뽑지 않는 경우

 

2. 가장 큰 손해가 되는 것

멀티탭에서 플러그를 뽑았는데 뒤에 뽑은 가전제품이 등장해 다시 플러그를 뽑는 경우

이를 조합해 가장 이득을 보기 위해선 "멀티탭에서 플러그를 뽑을 때 뒤에 가전제품이 다시 등장하지 않는 플러그를 뽑는다."라는 그리디 규칙이 생긴다! 

하지만 뽑아야 할 플러그 전부가 나중에 다시 등장하는 경우도 있다. 그렇다면 "당장 이득을 보는" 그리디적 생각을 한다면 가장 늦게 등장하는 플러그를 뽑으면 최소한 해당 플러그의 가전제품이 나올 때 까진 이득이다! 

아래 그림을 예시로 보자

1,2이 있는 멀티탭에 3을 넣어야 되면 빈자리가 없으므로 1이나 2 중 1개를 뽑아야한다. 이때 다음 1이 나오는 순서는 3번뒤이고 다음 2가 나오는 순서는 2번 뒤이다. 그러므로 현재 시점에선 1을 뽑아야 플러그를 뽑은 횟수가 적은 시간을 2를 뽑은 것 보다 1턴 길게 가져갈 수 있다. 그러므로 1을 뽑는 것이 이득이다.

즉 앞으로 등장하지 않거나 가장 늦게 나오는 가전제품을 뽑는 조건을 달면 가장 최소로 플러그를 뽑는 횟수를 구할 수 있다!

 

그리디로 풀었을 때 시간복잡도를 구해보자

---

그리디 알고리즘으로 풀었을 때 이를 시간 복잡도로 표현하면 다음과 같다.

 O(n)
= (모든 전자제품 탐색) * (플러그에 꽂혀있는 전자제품) * (다음으로 나오는 전자제품 순서 탐색)
= n*n*n
= n^3

최대 n은 100이기 때문에 100^3 = 1,000,000으로 제한시간인 2초인 연산횟수 2억보다 더 작아 제한시간내로 풀 수 있다!

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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[]input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = input[0];
        int K = input[1];

        int[] appliances = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        Set<Integer> plug = new HashSet<>();

        int count = 0;

        for(int i=0;i<appliances.length;i++){
        	//꽂을 자리가 있는 경우
            if(plug.size() < N){
                plug.add(appliances[i]);
            }
            //이미 멀티탭에 꽂혀있는 경우
            else if(plug.contains(appliances[i])){
                continue;
            }
            //멀티탭에 자리가 없는 경우
            else{
                PriorityQueue<Plug> pq = new PriorityQueue<>();

				//가장 늦게 등장하는 전자제품의 위치를 찾는 부분
                for(int p : plug){
                    Plug next = new Plug(Integer.MAX_VALUE,p); //없는 경우 = 최대값

                    for(int j=i+1;j<appliances.length;j++){
                        if(appliances[j] == next.type){
                            next.idx = j;
                            break;
                        }
                    }

                    pq.add(next);
                }

                Plug target = pq.poll();

                plug.remove(target.type);
                plug.add(appliances[i]);
                count++;
            }
        }

        System.out.println(count);
    }
}

class Plug implements Comparable<Plug> {
    int idx; //위치
    int type; //전자제품 종류

    public Plug(int idx, int type){
        this.idx = idx;
        this.type = type;
    }

    @Override
    public int compareTo(Plug o) {
        return o.idx -this.idx;
    }
}​

 

 

실행 결과

---

 

 

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

 

키워드

---

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

 

팁

---

1.그리디 알고리즘을 사용한다면 현재 시점에 가장 이득이 되는 조건과 손해를 보는 조건을 찾는데 집중하자.

2. 점화식을 찾으려해도 안나오면 그리디를 고려하자.