9436 Round Robin

처음에 erase 안 쓰고 true, false 값을 따로 둬서 구하려고 했었다.

그리고 나머지 연산 써서 인덱스로 계산하려고 했는데 너무너무 복잡했다. 

 

그렇게 삽질 하다가 안 되겠다 싶어서 그냥 그대로 구현했다. 

나머지 연산도 안 하고 그냥 1씩 계속 더했다.. 진작 이렇게 풀껄

 

T가 100이고 N이 100이어서 시간 내로 충분히 돌아간다. 

erase 쓰더라도 잘 돌아간다ㅋㅋ (참고 : erase()의 시간 복잡도는 N이다)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

bool    check(vector<int> &v) {
    for (int i = 0; i < v.size() - 1; i++) {
        if (v[i] != v[i+1])
            return false;
    }
    return true;
}

void    printv(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        printf("%d ", v[i]);
    }
    printf("\n");
}

void    solve(int n, int m) {
    vector<int> v(n);
    int start = 0;
    
    while(true) {
        for (int i = 0; i < m; i++) {
            v[(i + start) % v.size()]++;
        }
        
        int r = m % v.size();
        if (r == 0)
            r = v.size();
        
        v.erase(v.begin() + (start + r - 1) % v.size());
        start = (start + r - 1) % (v.size() + 1);
        
        if (start == v.size())
            start = 0;
        
        
        if(check(v))
            break;
    }
    
    printf("%d %d\n", v.size(), v[0]);
}

int main() {
    int n, m;
    
    while (1) {
        scanf("%d", &n);
        if (n == 0)
            break;
        scanf("%d", &m);
        
        solve(n, m);
    }
    
    return 0;
}

 

처음에 한 번 틀렸었다. 원인은 v.erase()를 하고 난 다음 start를 계산할 때 v.size() 값이 달라져서 문제였다. 

그래서 v.size()값을 기준으로 계산한 뒤 만약 start값이 배열의 범위를 넘어서면 0으로 돌아가게 구현했다.

erase 사용할 때 조심해야겠다.