[BOJ] 10104. Party Invitation (C++)

• 코딩 초보 

---

 

10104. Party Invitation 

You are hosting a party and do not have room to invite all of your friends. You use the following unemotional mathematical method to determine which friends to invite.

Number your friends 1, 2, . . . , K and place them in a list in this order. Then perform m rounds. In each round, use a number to determine which friends to remove from the ordered list.

The rounds will use numbers r1, r2, . . . , rm. In round i remove all the remaining people in positions that are multiples of ri (that is, ri, 2ri, 3ri, . . .) The beginning of the list is position 1.

Output the numbers of the friends that remain after this removal process.

 

The first line of input contains the integer K (1 ≤ K ≤ 100). The second line of input contains the integer m (1 ≤ m ≤ 10), which is the number of rounds of removal. The next m lines each contain one integer. The ith of these lines (1 ≤ i ≤ m) contains ri (2 ≤ ri ≤ 100) indicating that every person at a position which is multiple of ri should be removed.

 

The output is the integers assigned to friends who were not removed. One integer is printed per line in increasing sorted order.

 

#include <iostream>
#include <algorithm>
#include <list>
using namespace std; 

int k, m; 


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >>k>>m;
	list<int> lst; 

	for (int i = 0; i < k; i++) {
		lst.push_back(i + 1); 
	}

	std::list<int>::iterator it; //list 반복자 it 선언 
	for (int i = 0; i < m; i++) {
		int r = 1,j = 1; 
		cin >> r; 
		it = lst.begin(); 

		while (it != lst.end()) {
			if (j % r == 0) it = lst.erase(it++);
			else it++;
			j++; 
		}
	}

	for (it = lst.begin(); it != lst.end(); it++) {
		cout << *it << "\n"; 
	}
	
}

 

round m이 입력되면 m의 그 배수들을 배열 항목에서 삭제시켜주는 프로그램을 작성해야한다. list를 사용하여 1부터 k까지의 수를 저장시킨다. 여기서 iterator 반복자를 사용해줬다. 사용법은 다음 블로그의 글을 참고하였다. (https://spenshi.tistory.com/entry/C-%EB%B0%98%EB%B3%B5%EC%9E%90iterator) 

 

erase를 해주었을때 무효화가 발생할 수 있으므롤(list는 발생 안하지만 vector에서는 발생) 

습관을 들이기 위해 it=lst.erase(it++)를 통해 갱신해준다. 

그리고 for 반복문을 통해 *it로 접근하여 배열에 남아있는 수들을 출력해준다.