티스토리 뷰
https://www.acmicpc.net/problem/1168
1~n 까지 배열을 만들고 인덱스를 업데이트 하면서 해당 인덱스 값을 빼오고 배열에서 제거한 후 다음 인덱스로 넘어갑니다.
인덱스 업데이트 과정
x번째 인덱스에서 값을 빼왔으면 다음 인덱스는 x+(m-1) 입니다. 그 이유는 x번째 인덱스를 제거한 후 이동하기 때문에 인덱스가 한칸 씩 당겨지고 +m-1만 이동해도 +m번째 인덱스에 접근하는 것과 같은 효과가 나옵니다.
그런데 x+(m-1)의 값이 전체 배열의 크기를 넘어갈 수 있으므로 (x+(m-1))%(현재 배열의 크기)로 나머지만 구하여 인덱스가 범위를 넘어갈 경우 다시 0번부터 접근 가능하게 해줍니다.
예를 들어 아래 표의 3번째 줄 인덱스는 4+(3-1) % 5 == 1 입니다.
이 과정을 배열의 원소가 없어질 때까지 합니다. (혹은 정답 배열의 크기가 n이 될 때까지)
index |
answer |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
2 |
3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
4 |
36 |
1 |
2 |
4 |
5 |
6 |
7 |
|
1 |
362 |
1 |
2 |
4 |
5 |
7 |
|
|
3 |
3627 |
1 |
4 |
5 |
7 |
|
|
|
2 |
36275 |
1 |
4 |
5 |
|
|
|
|
0 |
362751 |
1 |
4 |
|
|
|
|
|
0 |
3627514 |
4 |
|
|
|
|
|
|
C++ code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> #include <vector> using namespace std; int main(){ int n, m; cin >> n >> m; vector<int> arr(n); for(int i = 0; i < n ; i++){ arr[i] = i+1; } int index = 0; vector<int> answer; while(!arr.empty()){ index = (index + m -1 )%arr.size(); answer.push_back(arr[index]); arr.erase(arr.begin()+index); } cout << "<"; for(int i = 0; i < n; i++){ cout << answer[i]; if(i < n-1) cout << ", "; } cout << ">"; return 0; } | cs |