[백준] 1700번 멀티탭 스케줄링

[문제]

사용할 전자 기기의 순번이 정해져있고 멀티탭에서 가장 적게 콘센트를 뽑으면서 모든 전자기기를 사용하고 싶을 때, 콘센트 뽑는 횟수의 최소값은?

 

[풀이]

크게 3가지 정도로 나눠서 풀이할 수 있습니다.

1. 멀티탭이 비어있을 경우

2. 다음 순번의 기기가 이미 멀티탭에 꽂혀있는 경우

3. 다음 순번의 기기가 멀티탭에 없을 경우 -> 제일 마지막에 다시 사용되거나 사용될 일 없는 기기 찾기

 

처음에는 너무 복잡하게 생각해서 정답은 맞췄지만 코드가 100줄이 넘어갔는데

풀이를 정리해서 큰 틀부터 정리해 나가니 코드가 반토막이 났습니다...

 

이미 멀티탭에 꽂혀있는 전자기기의 경우는 따로 boolean array를 통해 구분하여

추가적인 서치가 필요 없도록 했습니다.

 

아래는 해당 코드입니다!

 

#include <iostream>
#include <algorithm>
using namespace std;
int tab[100] = { 0 };
bool in_use[101] = { false };
int main(void){
    int n, k;
    int schedule[100];
    int cnt = 0;
    int full_check_cnt = 0;
    cin >> n >> k;
    for (int i = 0; i < k; i++) cin >> schedule[i];
    for (int i = 0; i < k; i++) {
        // 1. 멀티탭이 비어있을 경우
        if (full_check_cnt < n) {
            if (!in_use[schedule[i]]) {
                tab[full_check_cnt++] = schedule[i];
                in_use[schedule[i]] = true;
            }
        }
        else {
            // 2. 다음 순번의 기기가 이미 멀티탭에 꽂혀있을 경우는 무시
            // 3. 다음 순번의 기기가 멀티탭에 없을 경우
            if (!in_use[schedule[i]]) {
                // 제일 마지막에 다시 사용되거나 사용될 일 없는 기기 찾기
                int last_idx = 0;
                int change_idx = 0;
                // 현재 탭에 꽂혀있는 기기 loop
                for (int j = 0; j < n; j++) {
                    int tmp_idx = -1;
                    // i 이후의 스케쥴에 있는 기기 loop
                    for (int z = i + 1; z < k; z++) {
                        if (tab[j] == schedule[z]) {
                            tmp_idx = z;
                            break;
                        }
                    }
                    // 이후에 쓰이지 않을 기기일 경우 바로 뽑아버리
                    if (tmp_idx < 0) {
                        change_idx = j;
                        break;
                    }
                    else {
                        if (last_idx < tmp_idx) {
                            last_idx = tmp_idx;
                            change_idx = j;
                        }
                    }
                }
                // 사용중 여부(멀티탭 꽂힘 여부) 변경
                in_use[tab[change_idx]] = false;
                cnt++;
                tab[change_idx] = schedule[i];
                in_use[tab[change_idx]] = true;
            }
        }
    }
    cout << cnt;
    return 0;
}

 

질문, 지적사항 댓글 남겨주세요 :)