반갑습니다!

5567번: 결혼식 www.acmicpc.net 풀이 상근이의 번호가 1번이므로 1번에서 시작해서 BFS로 친구의 친구까지 확인해주면 된다. 코드 C++ #include #include #include using namespace std; int n, m; vector adj; int bfs() { queue q; vector visit(n + 1, false); q.push(1); visit[1] = true; int answer = 0; int count = 0; while (!q.empty()) { int size = q.size(); if (count == 2) break; while (size--) { int current = q.front(); q.pop(); for (int i : adj[c..

1939번: 중량제한 www.acmicpc.net 풀이 시간 초과와 메모리 초과가 발생하기 쉬운 문제이다. 결론부터 얘기하면 DFS + 이분탐색 또는 BFS + 이분탐색으로 해결할 수 있다. 문제를 읽어보면 그래프 탐색 문제이므로 DFS / BFS를 사용해야하는 것은 쉽게 알 수 있다. 그런데 문제에서 C가 최대 1,000,000,000이 되기 때문에 물품의 최대값을 찾을 때 선형 탐색으로는 찾을 수 없다는 것을 알 수 있다. 따라서 Parametric Search (이분 탐색)을 사용해 가능한 물품의 무게를 찾아서 시간 초과를 방지할 수 있다. 그리고 N의 최댓값이 10,000이므로 인접 행렬을 사용하면 메모리 초과가 발생한다. 따라서 인접 리스트를 통해 메모리 초과를 방지해서 해결했다. 코드 C++ ..

1822번: 차집합 www.acmicpc.net 풀이 집합 B를 Set에 담고 A의 원소들을 탐색해서 답을 찾았다. 코드 C++ #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n1, n2; cin >> n1 >> n2; vector a(n1); set b; for (int i = 0; i > a[i]; for (int i = 0; i > tmp; b.insert(tmp); } vector answer; for (int num : a) { if (b.find(num) ==..

1715번: 카드 정렬하기 www.acmicpc.net 풀이 가장 작은 숫자의 카드끼리 섞어야한다는 것은 직관적으로 알 수 있다. 따라서 우선순위 큐를 사용해서 구현했다. 코드 C++ #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; priority_queue pq; for (int i = 0; i > tmp; pq.push(tmp); } int ans = 0; while (pq.size() > 1) { int n1 = pq.top(); pq.pop(); int n2 = pq.top(); pq.pop(); int..

2012번: 등수 매기기 www.acmicpc.net 풀이 문제의 관건은 각 학생들이 본인이 희망하는 등수와 실제 등수의 차이가 적어야한다는 점이다. 아이러니하지만 5등을 희망하는 선수가 1등을 하면 불만도 4가 쌓인다. 5등을 희망하는 학생은 4등이나 5등, 6등 등을 받는 것이 훨씬 좋다는 얘기이다. 따라서 희망 등수를 오름차순으로 정렬한 뒤, 1등부터 차례로 순위를 부여해주면 된다. 코드 C++ #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; vector s; cin >> n; for (int i = 0; i < n; i++) { int..