소근소근

백준 3665 최종 순위 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬 문제이다. 2차원 배열에 edge를 저장하는 방식으로 풀었다. int nf, nt; cin >> nf >> nt; /*if (adj[nt][nf] == 1) { adj[nt][nf] = 0; indegree[nf]--; } adj[nf][nt] = 1; indegree[nt]++;*/ if (adj[nf][nt]) { adj[nf][nt] = 0; adj[..

백준 2056 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬 문제이다. 1516 게임개발 문제와 매우 비슷하다. https://steptoprogrammer.tistory.com/57 [백준 BOJ 1516 gold3 - 게임 개발] 위상정렬(topological sort) C++ 백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수..

백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 어떤 건물을 짓기 전에 먼저 지어야 하는 건물이 있다는 조건에서 위상정렬을 떠올릴 수 있다. #include #include #include #include #include #include #include using namespace std; int N; int period[501]; vector adj[501]; int indegree[501]; int dab..

백준 문제집 1766 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1부터 N까지의 문제를 푸는 순서를 출력한다. 조건은 두가지다. 1. 되도록 쉬운 문제 먼저 푼다.(작은 숫자 문제 먼저 풀어야 한다) 2. 먼저 푸는 문제가 있으면 먼저 풀어야 한다. (두 문제 간에 우선순위가 있다.) 문제 간의 우선순위를 지키면서, 쉬운문제를 풀어야 한다. 1번조건을 충족하기 위해서 우선순위 큐를 사용하고, 2번 조건은 위상..