개요

[링크]백준 1700번: 멀티탭 스케쥴링

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

접근 방식

• 첫 번째 방식
  그냥 단순히 멀티탭에 꽂힌 플러그들에서 사용 순서 제일 늦은 것부터 뽑는 방식으로 접근했다.
  이렇게 되면 예를들어 멀티탭 구멍이 3개일 때,
  2 3 4 7 1 7 5 7 이런식으로 들어오면 7이 제일 빈번하게 들어옴에도 불구하고 7을 계속 빼서 틀렸다.

• 두 번째 방식
  첫 번째는 꽂으려는 가전제품이 멀티탭에 꽂혀있나 체크,
  두 번째는 멀티탭에 비어있는 구멍이 있나 체크,
  세 번째는 들어오려는 모든 가전제품을 조사해
  제일 늦게 들어오는 것부터 빼기.

코드

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

vector<int> multiTap;
vector<int> plugs;

void input(int& holes, int& usedAmount) {
	int tempInput = 0;
	cin >> holes >> usedAmount;
	for (int i = 0; i < usedAmount; i++) {
		cin >> tempInput;
		plugs.push_back(tempInput);
	}
		multiTap.assign(holes,0);
	

}

void solution(int& holes,int& usedAmount) {
	int ans = 0;
	for (int i = 0; i < usedAmount; i++) {
		bool plugged= false;					//플러그에 꽂았나.
		for (int j = 0; j < holes; j++)			//멀티탭에꼽으려는 플러그가 있을 때 
		{
			if (multiTap[j] == plugs[i]) {
				plugged = true;
				break;
			}

		}
		
		if (plugged) continue;
		for (int j = 0; j < holes; j++) {		//멀티탭이 비어있을 때	
			if (multiTap[j] == 0) {
				multiTap[j] = plugs[i];
				plugged = true;
				break;
			}
		}
	
		if (plugged) continue;

		int lastNeed = -1;								//마지막으로 들어올 차례
		int index = -1;									//뺄 멀티탭 인덱스

		for (int j = 0; j < holes; j++) {				//이제 사용횟수 없거나 멀티탭중에 제일 뒤에 들어올 놈 빼야함
        												//멀티탭의 각 플러그들이랑 앞으로 들어올 플러그들 비교
			int tmp = 0;
			for (int k = i + 1; k < usedAmount; k++) {	//k는 i+1부터 조사, 왜냐면 i일때는 line96에서 조사하기때문
				if (plugs[k] == multiTap[j])			
					break;
				tmp++;									//멀티탭에 꽂힌 플러그들이 들어올때 까지 tmp++
                										//이런식으로 구현시 아예 안들어올 플러그들은 tmp가 무조건 제일 많아서
                                                        // 바로 멀티탭에서 바로빠진다
			}
			if (tmp > lastNeed) 						//tmp가 가장 큰 값 lastneed에 넣고 그 인덱스 저장
			{
				lastNeed = tmp;
				index = j;
			}
		}
		multiTap[index] = plugs[i];
		ans++;

	}
	cout << ans;
}

int main() {
	int holes = 0,usedAmount=0;
	input(holes,usedAmount);
	solution(holes,usedAmount);
}

문풀후생

인터넷을 찾아보고 대부분의 풀이들이 채택한 방식을 공부하며 적어봤는데 계속 틀렸다.
반나절을 계속 뭐가 틀린지 고민했는데,
알고보니 멀티탭에 해당 플러그가 꽂혀있는지 체크하기전에
멀티탭에 그냥 다 갖다 박아서 멀티탭이 하나라도 비어있다면 같은 값이 중복으로 멀티탭에 들어가서 틀린것이였다...