2022.07.04 ㅠㅠ
전체 글
- 2021.01.05 2021.02.20
- BOJ 1713 후보 추천하기 2021.01.01
- BOJ 13913 숨바꼭질 4 2020.12.28
2021.01.05
2021. 2. 20. 13:19
BOJ 1713 후보 추천하기
2021. 1. 1. 22:11
1713번: 후보 추천하기
첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로
www.acmicpc.net
구현, 시뮬레이션 문제
- 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
- 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
- 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
- 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
- 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
N이 주어지면 N칸만큼 사진이 게시되어야 하는데 문제를 이해하기에 어려운 내용은 아니다.
구현에 있어서 살짝 까다로운 부분이 있다면 3번이다.
우선 나는 풀이를 구현하는데 있어 vector<pair<int,int>> 를 선언해주고
number와 몇 번 불렸는지 cnt로 사용했다.
우선 벡터에 push_back으로 추가되니 추천 받은 횟수가 가장 적은 학생이 두명 이상일 경우 앞에 있는 것을 지워주면
되는데 이것은 erase 메소드로 쉽게 처리할 수 있다.
또한 C++에는 <algorithm> 헤더 파일에 min_element() 가 존재하는데 람다 함수를 이용해서
pair<> 로 접근하는 것들에 대해서 쉽게 처리해줄 수 있다.
min_element(a.begin(), a.end(), [](const auto& lhs, const auto& rhs) {
return lhs.second < rhs.second;
})
이런 식으로 사용해주면 second가 가장 작은 원소를 찾아 그 iterator를 반환해준다.
전체 소스 코드
|
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
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
vector<pair<int, int>> a;
const int inf = 1e9;
inline bool f(int key) {
for (auto& i : a)
if (i.first == key) {
++i.second; return true;
}
return false;
}
void add(int x) {
if (a.size() < n) a.push_back({ x,1 });
else {
a.erase(min_element(a.begin(), a.end(), [](const auto& lhs, const auto& rhs) {
return lhs.second < rhs.second;
}));
a.push_back({ x,1 });
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> x;
if (!f(x)) add(x);
}
sort(a.begin(), a.end());
for (auto i : a) cout << i.first << ' '; cout << endl;
return 0;
}
|
cs |
'BOJ' 카테고리의 다른 글
| BOJ 13913 숨바꼭질 4 (0) | 2020.12.28 |
|---|---|
| BOJ 13549 숨바꼭질 3 (0) | 2020.12.28 |
| BOJ 12851 숨바꼭질 2 (0) | 2020.12.28 |
| BOJ 15686 치킨 배달 (0) | 2020.12.25 |
| BOJ 3190 뱀 (0) | 2020.12.19 |
BOJ 13913 숨바꼭질 4
2020. 12. 28. 22:20
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
이번 문제는 경로를 추적해서 출력하는 문제였다.
조금만 생각해보면 금방 알 수 있는데, 현재 위치를 지나가는 배열 a를 만들어서
a[next] = cur 를 담고있다고 가정해보면 a[k] 에는 k에 도착하기 전 가장 마지막 위치가 담겨있을 것이고,
a[마지막 위치] 에는 그 위치에 오기 위한 위치가 점진적으로 들어있을 것이다.
그렇다면 구현은 간단하다.
기존 bfs를 통해 최단시간을 구할 때 a[next] = cur 만 추가해주고 이후에 재귀적인 호출을 통해
역추적해주면 된다.
|
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
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#include <queue>
using namespace std;
int a[100001], n, k;
int vis[100001];
queue<int> q;
void backtrace(int cur) {
if (cur == n) {
cout << n << ' '; return;
}
backtrace(a[cur]);
cout << cur << ' ';
}
int main() {
cin >> n >> k;
q.push(n);
while (!q.empty()) {
int cur = q.front(); q.pop();
if (cur == k) break;
for (int i : {cur - 1, cur + 1, cur * 2}) {
if (0 <= i && i <= 100000 && !vis[i]) {
vis[i] = vis[cur] + 1;
q.push(i);
a[i] = cur;
}
}
}
cout << vis[k] << endl;
backtrace(k);
cout << endl;
return 0;
}
|
cs |
'BOJ' 카테고리의 다른 글
| BOJ 1713 후보 추천하기 (0) | 2021.01.01 |
|---|---|
| BOJ 13549 숨바꼭질 3 (0) | 2020.12.28 |
| BOJ 12851 숨바꼭질 2 (0) | 2020.12.28 |
| BOJ 15686 치킨 배달 (0) | 2020.12.25 |
| BOJ 3190 뱀 (0) | 2020.12.19 |