1158 조세퍼스 문제

으으 어떻게 푸는지는 나와있는데 구현하는게 힘들었다. 벡터를 지우고 인덱스 앞당기고 으으으

처음에는 위와 같이 생각했다. k번째 수를 지워야 하는데 지우면 인덱스가 바뀌니깐 count로 k번찌인지 확인하고 i는 배열의 끝까지 가면 다시 처음부터 확인하도록.. 

 

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

int main() {
    int n, k;
    vector <int> v;
    scanf("%d %d", &n, &k);
    
    for(int i = 1; i <= n; i++){
        v.push_back(i);
    }
    
    int count = 1;
    
    vector<int>::iterator iter;
    for(iter = v.begin(); ; iter++){
        printf("%d\n", *iter);
        if(iter == v.end())
            iter = v.begin();
        
        if(count == k){
            printf("count : %d\n", *iter);
            v.erase(iter);
            count = 0;
        }
        
        if(v.empty())
            break;
            
        count++;
    }
    
    return 0;
}

구현할때는 배열의 원소를 지워야 하는데 구글링 해보니깐 erase를 쓰면 된다고 했다. 근데 얘는 인자를 iterator로 받아야 한대서 코드를 저렇게 적었다. (낯설다) 결국 안 돌아가서 그냥 이거 말고 익숙한 int i 를 썼다. 

 

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

int main() {
    int n, k;
    vector <int> v;
    vector <int> p;
    scanf("%d %d", &n, &k);
    
    for(int i = 1; i <= n; i++)
        v.push_back(i);
    
    int count = 1;
    for(int i = 0; ; i++,count++){
        if(i == v.size())
            i = 0;
            
        if(count == k){
            p.push_back(v[i]);
            v.erase(v.begin() + i);
            i--;
            count = 0;
        }
        
        if(v.empty())
            break;
    }
    
    printf("<%d", p[0]);
    for(int i = 1; i < n; i++)
        printf(", %d", p[i]);
    printf(">");
    
    
    return 0;
}

v.erase(v.begin() + i);

erase도 이렇게 적으면 된다. 

 

처음에 erase를 하면서 출력하고 싶었는데 <, , , > 이 형식으로 출력을 못하겠어서 결국 벡터를 하나 더 만들어서 출력했다. 

 

---

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

int main() {
    int n, k;
    vector <int> v;
    vector <int> p;
    scanf("%d %d", &n, &k);
    
    for(int i = 1; i <= n; i++)
        v.push_back(i);
    
    int pos = 0;    //현위치
    while (!v.empty()){
        pos = (pos + k - 1) % v.size();
        p.push_back(v[pos]);
        v.erase(v.begin() + pos);
    }
    
    printf("<%d", p[0]);
    for(int i = 1; i < n; i++)
        printf(", %d", p[i]);
    printf(">");
    
    
    return 0;
}

이렇게 짤 수도 있다. 계속 값을 더해가면서 없애주는데 크기를 넘어서면 나눠서 뱅뱅 돌게 만든다.

 

 

뇌가 손에 달렸나.. 적어가며 해야지 이해가 된다.