백준 1700번 _ 멀티탭 스케줄링

2020-05-07 · 배운 것 · 5분 읽기

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

풀이방법

현재 연결되어 있는 가전제품중에 이후에 제일 늦게 사용되거나 더이상 사용되지 않는 가전제품을 빼고 연결하면 된다.

처음에 이 내용에 도달하기까지 생각하기 힘들었다. 위의 내용은 컴공학부생이라면 OS수업때 들었을 프로세스 스케줄링기법중 하나라고 한다. 수학적으로 증명된 기법이라는데 정확한 내용은 찾지 못했다. 하지만 조금이라도 언급한 블로그는 여기다.
https://eine.tistory.com/entry/%EB%B0%B1%EC%A4%80-1700%EB%B2%88-%EB%A9%80%ED%8B%B0%ED%83%AD-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

백준 1700번 멀티탭 스케줄링 문제 풀이

다음은 분기점이다. 여기까지 생각이 닿으면 나머지는 그냥 코딩이다.

전체코드

#include <iostream>
#include <vector>

using namespace std;

bool isPlug[101];
int order[101];
int N, K;

void Input()
{
	cin >> N >> K;
	for (int i = 1; i <= K; i++)
		cin >> order[i];
}

void solve()
{
	vector<int>multitap;
	int cnt = 0;
	for (int i = 1; i <= K; i++)
	{
		int object = order[i];
		if (isPlug[object] == true)
			continue;
		else
		{
			//아직 자리가 남아있을때
			if (multitap.size() < N)
			{
				isPlug[object] = true;
				multitap.push_back(object);
			}
			else
			{
				// 가장 멀리 있거나 없는것 찾기
				int popIdx = 0;
				int popDist = 0;
				bool isEnd = false;
				for (int j = 0; j < (int)multitap.size(); j++)
				{
					if (isEnd)
						break;
					int value = multitap[j];
					for (int k = i + 1; k <= K; k++)
					{
						if (order[k] == value)
						{
							if (popDist < k - i)
							{
								popDist = k - i;
								popIdx = j;
							}
							break;
						}
						//끝까지 같은게 없으면 이거빼셈
						if (k == K)
						{
							popIdx = j;
							isEnd = true;
						}
					}
				}

				//빼기
				isPlug[multitap[popIdx]] = false;
				multitap.erase(begin(multitap) + popIdx);
				//넣기
				multitap.push_back(object);
				isPlug[object] = true;
				cnt++;
			}
		}
	}

	cout << cnt;
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

다 정리하고 푸는데도 중간중간 계속 헷갈려서 진짜 답답했던 문제였다. 그리디 역시 제일싫다.