https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 오랜만에 문제를 풀어보았습니다. (사실 그 전에 푼 거 틀린 거 다시 풀기....) 주어진 그래프에서 경로의 최소 값 중 최대값을 구하면 됩니다. 여러 방법이 있지만 가장 쉽게 떠오르는 다익스트라를 이용해서 풀었습니다. 다익스트라가 경로를 탐색하면서 기존 결과보다 좋으면 업데이트를 반복하는 것이므로, 일반적인 다익스트라처럼 합을 계산하는 ..
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 그냥 간단한 외판원 문제입니다. 외판원 문제가 오랜만에 보여서 풀어보았는데 틀렸다고 해서 다른 외판원 문제 풀었던 코드로 넣으니 정답이 나왔습니다. (왜지???? 전혀 다른 점이 없었는데??? 눈을 잘 비벼보자.....) 특별한 조건은 없고, weight 가 항상 양수인 조건만 있습니다. 외판원이 노드를 방문하는 과정에서 dp[i][j] = i 번 노드..
https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 간단한 백트래킹 문제였습니다. 격자판을 백트래킹으로 탐색하면서 가능한 위치의 점이 여태 지나온 점들의 인접한 점과 일치하는 점인지 확인하면서 계산하면 됩니다. 그리고 가능한 점이면 해당 점의 인접한 점 또한 체크리스트에 포함시키면서 진행하면 됩니다. 코드는 다음과 같습니다. #include #include #include using namespace std; int n, m, k; in..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 0 ~ n-1 번 사람을 노드로 봤을 때 연속으로 노드가 5개 이어질 수 있느냐 없느냐의 문제입니다. dfs를 이용해서 해당 노드의 깊이가 4가 된 순간이 5개를 연속으로 탐색한 경우이므로 해당 경우가 발생하면 정답입니다. 코드는 다음과 같습니다. #include #include #include #include using namespace std; // 각 숫자 node로 보고 // 시작 노드로부터 dfs depth 4면 정답 // 5개 연결된 거랑 동일 int n, m; vector vec[2001]..
https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 수상 택시로 사람들을 태워다니면서 가는 최소 거리를 구하는 문제입니다. 태우는 사람에 대한 조건은 따로 없으니 순방향으로 가는 사람은 가는 길에 내려준다고 생각하면 총 M 만큼 이동합니다. 역방향으로 가는 사람은 스위핑 알고리즘을 이용한 선분 길이 구하는 것과 동일하게 계산하면서 x 2 만큼 길이를 구하면 됩니다. (역방향이므로 갔다가 다시 원래 방향으로 가야 함) 코드는 아래와 같습니다. #i..