반응형
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
일단 규칙을 파악해보면 n = 7, k=3 일 때
12[3]45[6]7
12[4]57
[1]25[7]
이런식으로 []안에 있는 것을 출력할 것이다.
쉽게 생각해보면 자기 차례가 아닌 것을 뒤로 보내주면 연결이 된다.
12[3]45[6]712[4] 이런식으로 말이다.
바로 queue를 쓰면 쉽게 이 방식을 구현할 수 있다.
자기 차례가 아니면 뒤로 옮겨주고 자기 차례인 경우 pop을 해주면 된다.
ps. 출력 형식이 <> 안에 있으니 주의 하도록 하자.
단계별 풀이
1. 정답을 저장할 vector와 사이클을 돌릴 queue 선언
2. 큐가 empty가 될 때 까지 반복
3. k-1 만큼 수를 뒤로 보냄 (front를 push 후 pop)
4. k번째 일 때 수를 vector에 저장하고 pop
5. 출력
전체코드
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
27
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
int n, k;
vector<int> v;
queue<int> q;
cin >> n >> k;
for (int i = 1; i <= n; i++){
q.push(i);
}
while(!q.empty()){
for (int i = 0; i < k-1; i++){
q.push(q.front()); // 자기 차례가 아닌 경우 수를 뒤로 보냄
q.pop();
}
v.push_back(q.front());//차례 도달 시
q.pop();
}
cout << "<";
for (int i = 0; i < n-1;i++){
cout << v[i] << ", ";
}
cout << v[n - 1] << ">";
return 0;
}
|
cs |
체감난이도 | 걸린시간 | 참고 | 후기 | 사용 문법 |
하 | 28min | x | 출력 형식 지키지 않아 조금 오래걸렸음.... | queue |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 10799 쇠막대기 c++ [컴공과고씨] (0) | 2022.04.16 |
---|---|
백준 9012 괄호 c++ [컴공과고씨] (0) | 2022.04.16 |
백준 11650 좌표 정렬하기 c++ [컴공과고씨] (0) | 2022.04.12 |
백준 23284 모든 스택 수열 c++ [컴공과고씨] (0) | 2022.04.12 |
백준 12865 평범한 배낭 c++ [컴공과고씨] (0) | 2022.04.09 |