(C++) - 백준(BOJ) 10104 : Party Invitation

https://www.acmicpc.net/problem/10104

10104번: Party Invitation

자료구조를 사용하는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

친구 수 k, list에서 지워지는 단위 m, 친구 list friends, 지워지는 x번째 번호들이 담길 removal, 지워졌는지 여부를 판단할 list isRemoved를 vector형으로 선언해 준 뒤 적절히 입력받습니다. 이 후 입력받은 만큼 vector의 크기를 resize함수로 조절해줍니다.

📔 풀이과정

removal[x]의 배수들이 매 라운드 friends 목록에서 지워지게 됩니다. 따라서 배수만큼 for loop를 수행하며isRemoved[friends[removal[x*i라운드]]를 1로 만들어줍니다.

isRemoved가 0인 살아남은 친구들만 updatedFriends에 친구번호들을 저장해줍니다.

friends에 갱신된 updatedFriends를 배정해줍니다.

📔 정답출력

friends의 원소들을 1번째 index부터 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

int k,m;
vector <int> friends, removal, isRemoved;

int main(){
    cin >> k >> m;

    friends.resize(k+1);
    removal.resize(m);
    isRemoved.resize(k+1);

    for(int i = 0; i < m; i++) cin >> removal[i];
    for(int i = 1; i <= k; i++) friends[i] = i;

    for(auto re : removal){
        int sz = friends.size();
        vector <int> updatedFriends;

        for(int i = 1; re * i <= sz; i++) isRemoved[friends[re*i]] = 1;

        for(int i = 0; i <= k; i++)
            if(!isRemoved[i]) 
                updatedFriends.push_back(i);

        friends = updatedFriends;
    }

    for(int i = 1; i < friends.size(); i++) cout << friends[i] << '\n';
}