[BOJ] 백준 9436 Round Robin

출처: www.acmicpc.net/problem/9436

 Input 
5 17
7 10
90 2
0　 

 Output 

2 13

5 3

45 1

운영체제 (OS) 사용되는 Round Robin을 구현해보는 문제이다

문제에서는 주어진 T 만큼 count를 나눠가진다.

　

① 주어진 T만큼 List에 남아있는 Node의 count를 올려줍니다.

    List가 순환될 수 있도록 move()는 끝→시작으로 가도록 처리합니다.

    ※ 원형 큐를 생각하시면 좋습니다.

② 마지막에 추가 할당된 노드 제거

③ 남아 있는 노드들의 count가 동일하지 확인

해당 과정을 몇 번의 turn 가지는지 구한다.

---

#include <stdio.h>
 
const int MAX_N = 1e2 + 5;
int N, T;
struct Node {
    int count;
    Node* prev, * next;
    Node* alloc(Node* _prev, Node* _next) {
        count = 0;
        prev = _prev, next = _next;
        if (prev) prev->next = this;
        if (next) next->prev = this;
        return this;
    }
 
    void pop() {
        if (prev) prev->next = next;
        if (next) next->prev = prev;
    }
}buf[MAX_N], head, * last;
int bcnt;
 
void init() {
    scanf("%d", &T);
    head.next = NULL;
    bcnt = 0;
    for (int i = 0; i < N; i++) {
        buf[bcnt++].alloc(&head, head.next);
    }
    last = head.next;
}
 
bool checkCount() {
    for (Node* cur = head.next; cur; cur = cur->next) {
        if (head.next->count != cur->count) return false;
    }
 
    // 모두 일치하는 경우
    printf("%d %d\n", N, head.next->count);
    return true;
}
 
void move() {
    // List에서 포인터(last)가 순환되도록
    // 문제 조건상 리스트에는 적어도 1개 이상 존재.
    last = last->next;
    if (!last)  last = head.next;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    while (1) {
        scanf("%d", &N);
        if (N == 0) break;
 
        init();
 
        while (1) {
            for (int i = 1; i <= T; ++i) {
                // 포인터를 이동하면서 실행 횟수 up
                last->count += 1;
                // 마지막 순서가 아닌 경우에는 포인터 이동
                if (i != T) move();
            }
 
            // 마지막으로 실행된 Node를 List에서 제거
            last->pop();
            N--;
            move();
 
            // List에 남아 있는 Node의 count가 모두 동일한지 확인
            if (checkCount()) break;;
        }
    }
}