[BOJ/C++] 1700(멀티탭 스케줄링)

1. Link

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

2. 풀이 과정

1. 전기용품의 사용 순서에 따라 멀티탭에 순서대로 대입 -> dp 또는 그리디
2. 각 상태의 멀티탭에서 꽂거나 바꿔야하는 플러그 선택 -> 그리디

• DP와 그리디의 공통점은 Optimal Substructure을 가진다는 것이지만, 그리디로 풀게 된 가장 큰 이유는 Greedy choice property를 만족하는 문제라고 생각했기 때문입니다.

• DP는 미래의 선택이나 이전의 Subproblem과 연결적이지만, 그리디는 상대적으로 그러한 부분이 적기에(간단하게는 현 시점에서의 최적해를 찾는 것이므로) 그리디를 선택하였습니다.

• 그리디 알고리즘의 두 가지 조건은 다음과 같습니다.

1. 간단하게는 현재 시점에서의 최적해를 고를 수 있는가
2. 해당 문제에 대한 최적해가 Subproblem의 최적해를 포함하는가
   이 두가지를 만족할 경우 그리디 알고리즘을 사용할 수 있다고 볼 수 있습니다. 그리디와 DP의 차이는 별도로 글을 작성하여 차이점을 상세하게 살펴보도록 하겠습니다.
   

3. 정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, k;
int multitap[102];
int plug[102]{ 0 };

void input() {
	cin >> n >> k;
	for (int i = 1; i <= k; ++i) {
		cin >> multitap[i];
	}
}

void solution() {
	input();
	if (n >= k) {
		cout << 0;
		return;
	}
	int answer = 0;
	for (int i = 1; i <= k; ++i) {
		//1. if 플러그 꽂혀있으면 continue
		bool isAlready = false;
		for (int j = 1; j <= n; ++j) {
			if (plug[j] == multitap[i]) {
				isAlready = true;
				break;
			}
			//2. 리스트에 없는 경우
			//2-1. 플러그에 빈 곳 있는가 -> 있으면 거기에 삽입
			if (plug[j] == 0) {
				plug[j] = multitap[i];
				isAlready = true;
				break;
			}
		}
		if (isAlready) continue;
		//2-2. 플러그가 가득 찼는가 -> 다음 multitab 목록 보고 값 변경
		int latest = 0, index = n;
		for (int j = 1; j <= n; ++j) {
			int last = 0;
			for (int nxt = i + 1; nxt <= k; ++nxt) {
				if (plug[j] == multitap[nxt]) {
					break;
				}
				++last;
			}
			if (last > latest) {
				index = j;
				latest = last;
			}
		}
		plug[index] = multitap[i];
		++answer;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

4. Reference

https://en.wikipedia.org/wiki/Greedy_algorithm