https://www.acmicpc.net/problem/1956  1956번: 운동첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의www.acmicpc.net 풀이과정사이클이 생기는 부분의 최소합을 구하면 되는 문제이다.   i == j일 때는 continue 해주고, arr[i][j] + arr[j][i]일 때의 최솟값을 구하면 된다.   만약 res가 INF일 경우는, 사이클이 되는 곳이 한 곳도 없으므로 -1을 출력해준다. #include #include #include using namespace std;int V..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이과정 예전에 다익스트라 + 플로이드 와샬 문제를 푼 적이 있어서 비슷할 거라고 생각했다. 그러나 생각해야될 것이 많아서 시간이 오래 걸린 문제였다..! 처음에 풀었던 방식은 경유지를 지나면 res배열에 담아주는 방식이다. (2번째 코드) 그러나 이렇게 되면 1행 6열은 1 -> 2 -> 5 -> 6 두개의 경유지를 거치게 되어 첫번째 경유지 2가 아닌, 두번째 경유지인 5를 출력하게 되었다. 최초로 거..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이과정 예전에 풀었던 플로이드 와샬의 백준 키 순서와 비슷한 문제였다. 키 순서 문제 참고하기 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 입력을 받자마자 num[x][y] = 1, ..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이과정 문제에서 작년 순위를 주고, 순위가 바뀐 모든 팀의 정보를 주었으므로, 확실한 순위를 모르는 경우인 "?"인 경우는 없다. adj[a][b] = true : a팀 다음에 b팀 indegree[x] : x 앞에 와야 하는 팀 개수 #include #include #include #include #include #include using namespace std; int T, n, m..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 풀이과정 이때까지 풀었던 문제 유형들과는 다른 느낌이었다. 위상 정렬 함수를 만들지 않고 main함수 안에서 하려고 하니 더 어렵게 느껴졌다. 일단 입력을 M번 받아놓고 화살표 간선끼리 연결해주며 진입 차수도 플러스해준다. 그다음, K번 반복하는 부분이 중요한데 option이 1이면 건물을 1개 건설하는 것이고 2이면 파괴하는 것이라고 한다. 건설 부분을 보면 진입..

https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 풀이과정 문제를 잘 읽지 않고 풀어서 고생했던 문제이다... 가장 핵심인 부분은 "나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다"라는 부분이다. #include #include #include #include using namespace std; i..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 풀이과정 dp와 위상정렬을 같이 쓰는 문제다. 위상정렬 함수를 보면 진입차수가 0일 경우(1,4,6번 노드)에 큐에 푸시를 하며 정답 배열에 1을 넣어준다. 그리고 큐가 비어있지 않을 때까지 연결되어있는 노드를 돌며 dp를 해주며 최종적으로 max인 값(res)를 출력해준다. #include #include #include #include using namespace std; int N, M, A, B; int indegr..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이과정 위상 정렬 함수는 다른 문제와 동일하지만, 입력을 받고 벡터 함수에 넣는 것이 색다른 문제였다. 위 사진처럼 수를 입력받고, 부등호에 따라 이중 반복문으로 벡터 함수에 넣어주며 진입차수를 1씩 늘려주었다. 큐의 앞부분 now의 값을 res에 넣어주며 개수가 N개가 아닐 때는 순서를 정하는 것이 불가능하다는 뜻이므로 0을 출력해준다. #include #include #i..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이과정 dp와 위상 정렬을 같이 쓰는 문제이며 1005 ACM Craft 문제와 비슷한 문제이다. 이처럼 위상정렬과 dp가 같이 쓰이는 문제가 많은 것 같다. 풀이 과정은 1005번 문제와 같지만, 처음에 입력문에서 v를 푸시하는 과정에서 반대로 푸시를 해 고생을 먹었던 문제이다. 몇 번 노드에 몇 번 노드를 푸시해줄 것인지 방향을 잘 생각해서 입력받아야 한다. 도착점이 정해져있지 않으..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이과정 이 문제는 조건 3개를 잘 기억해야 한다. 1. N개의 문제는 모두 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 3. 가능하면 쉬운 문제부터 풀어야 한다. 문제를 읽어보면 1번 문제가 쉬운 문제이고 N번 문제가 가장 어려운 문제라고 하였으니 우선순위 큐를 떠올려 봐야한다. 원래 우선순위..