www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net (cin.eof())를 통해 종료 조건을 확인하는 것에 주의하였고, map tree를 통해 나무의 정보(나무 이름, 개수)를 저장하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; map tree; map::iterator it; int main() { cin.tie(NULL); ios_base::sync_with_stdi..

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 우선 시작 지점에서 각각 지점까지 다익스트라 알고리즘을 통해 최단경로를 구한다, 그리고 어떤 지점에서 어떤 지점으로 가는 최단 경로의 길이를 구하는 Find_dist함수를 만들어서 이를 통해 목적지 후보들 중 시작점에서 목적지까지 거리가 시작점에서 g까지의 거리 + g, h의 거리 + h에서 목적지까지 거리 또는 시작점에서 h까지의 거리 + h, g의 거리 + g에서 목적지까지 거리인지 확인한다. 코드 #..

www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net AB에 A[i] + B[j] 조합의 모든 경우를 저장하고, CD에 C[i] + D[j] 조합의 모든 경우를 저장하여 각각 정렬한 뒤, AB를 돌면서, 해당 값과 합이 0이 되는 수를 lower_bound를 통해 찾고, 만약 찾았다면 it_upper(upper_bound한 것) - it_lower(lower_bound한 것)를 계산하여 개수를 추가한다. 코드 #include #include #i..

www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상 정렬을 이용하였다. 그래프를 연결할 때 우선 작년 순위 기준으로 뒷순위로 가는 모든 연결을 하였다. 그리고 상대적인 순위가 바뀐 팀의 목록이 주어질 때 그 팀들의 연결을 수정하였다. 중간에 큐의 크기가 1이 아니라면 확실한 순위를 찾을 수 없다고 판단하고, 최종 결과 순위 목록의 크기가 n이 아니라면 순위를 정할 수 없다고 판단하였다. 코드 #include #include #include #incl..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬을 이용하였는데, 큐는 우선순위 큐를 써서 우선순위 큐에 풀 수 있는 문제를 저장할 때 (-문제 번호)를 저장하여 가능하면 쉬운 문제부터 풀도록 하였다. 코드 #include #include #include #include using namespace std; int n, m; vector adj[32001]; vector indegree(32001, 0); priority..

www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬을 이용하였고, install_time에 해당 건물의 설치 시간, plus_install_time에 해당 건물 설치 전에 추가되어야 되는 시간, all_install_time에 해당 건물이 완성되기 까지 걸리는 최소 시간을 저장하여 문제를 해결 했다. plus_install_time은 이전에 다수의 건물이 지어져야 될 때 그것들 중 총 완성 시간이 가장 큰 것이므로 그것들 중 총 완성 시간이 ..