4Legs_Archives

문제 링크 : www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 순위의 개념을 그래프에 위상 정렬을 적용하여 나타낼 수 있는가를 묻는 문제이다. 다만 초반 그래프를 구성하는 것이 다소 까다롭다. 위상 정렬 (Topological Sort) 위상 정렬 (Topological Sort) 방탈출 게임을 한다고 생각해 보자. 우리는 메인 룸에 있는 3개의 자물쇠를 풀어야 탈출에 성공하고, 다음 단계의 탈출에 도전할 수 있다. 3개의 열쇠는 메인 룸과 연 4le..

문제 링크 : www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 그래프의 단절점이란, 그래프에서 한 정점을 제거했을 때 그래프의 Connected Component가 증가하는 정점을 말한다. Connected Component는 DFS, BFS 등으로 그래프를 탐색했을 때 한 덩어리로 묶이는 정점들의 집합이라 이해하면 된다. 즉 그래프의 모든 정점을 발견하는 데 실행되는 탐색의 횟수와도 같다. 다음 그래프를 통해 단절점의 특징을 파..

문제 링크 : www.acmicpc.net/problem/15562 15562번: 네트워크 우리의 회사에는 N개의 네트워크 시스템 S1, S2, ..., SN와 이들을 연결하는 M개의 네트워크들 W1, W2, ..., WM이 있다. 네트워크 시스템들은 우선순위가 있어 모든 네트워크는 우선순위가 www.acmicpc.net 임의의 시스템 K에 대해 다음과 같은 경우를 생각해보자. 이 경우, 문제의 조건에 따라 네트워크를 정리하면 다음과 같다. 만약 K에서 B ~ F로 각각 나가는 간선이 하나씩 존재하더라도, 이 간선들은 모두 A에서 B ~ F로 나가는 간선으로 대체될 수 있다. 즉, 한 노드를 기준으로 자신에게 들어오는 간선이 존재한다면, 자신에게서 나가는 간선들은 위의 A -> B와 같이 대체될 수 있다..

문제 링크 : www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 주어진 무게추로 측정할 수 없는 최소무게를 구하는 문제이다. 무게추 1, 2, 3을 갖고 있다고 가정할 때, 우리는 1에서 6까지의 모든 무게를 측정할 수 있다. 이 상태에서 새로운 무게추 5가 추가되었을 때, 이미 우리는 1에서 6까지의 무게를 1~3 무게추로 측정할 수 있었기 때문에 각 무게에 대한 무게추 조합에 5 무게추만 추가한 새로운 조합을 만들어 낼 수 있다. 다시 말해 우리가 2, 3 무게추를 ..

문제 링크 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 이 문제를 DP로 풀기 위해 필요한 정보는 다음과 같다. ① 현재까지 그림을 산 사람들에 대한 정보 (한번 그림을 산 사람은 다시 살 수 없으므로) ② 마지막으로 그림을 산 사람 (다음에 살 사람의 가격은 마지막으로 산 사람에 의해 정해진다.) ③ 마지막으로 팔았을 때 그림의 가격 (다음에 살 사람은 이 가격 이상으로 사야 하기 때문) 따라서, 이 3가지 정보를 담은 3차원 dp 배열을 ..

문제 링크 : www.acmicpc.net/problem/20120 20120번: 호반우와 리듬게임 호반우가 모든 노트를 처리하면 3×1 + 4×2 + (-7)×3 + 1×4 = -6 점을 얻을 수 있습니다. 3번 노트를 제외한 모든 노트를 처리하면 3×1 + 4×2 + 1×1 = 12 점을 얻을 수 있습니다. 3번 노트를 놓쳤기에 4번 노 www.acmicpc.net DP문제의 대표유형인 계단오르기 문제와 유사한 문제이다. 각 노트를 처리하는 것과 계단을 한 번 오르는 것을 동일하게 생각한다면 수월하게 문제를 해결할 수 있다. 단 점수를 계산하기 위해선 현재까지 몇 콤보로 현재 노트를 처리하는지에 대한 정보가 필요하므로, 이 풀이에서는 dp 배열을 2차원으로 두었다. k번 노트를 c 콤보에서 처리한 경..

문제 링크 : www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 문제에서 주어진 레시피는, 한 물약을 만들기 위해 필요한 물약에 대한 정보이다. 즉, 레시피의 왼쪽에 있는 물약들을 모두 가지고 있어야 오른쪽의 물약을 만들 수 있다. 이는 곧 하나의 물약을 만들기 위해서는 다른 물약의 제조가 선행되어야 함을 의미하며, 따라서 이 문제를 위상 정렬 문제로 접근할 수 있다. 위상 정렬 (Topological Sort) 위상 정렬..

문제 링크 : www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 케이블의 교차점은 어떤 조건에서 발생할까? 다음과 같은 예시를 통해 알아보자. A열의 a번째 기계와 연결된 B열의 기계가 a'일 때, 이 기계와 케이블이 교차하기 위한 기계의 위치 (b, b')는 다음 조건을 만족한다. "b a' 또는 b > a AND b' a' 에 주목하자. 이 조건을 이용하면 우리는 두 열..

문제 링크 : www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제의 조건을 잘 살펴보자. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 제시된 조건들을 봤을 때 문제집의 문제 간에는 선행 관계가 존재함을 알 수 있으며, 따라서 이 문제는 사이클이 없는 방향 그래프 내에서 위상 정렬의 결과를 출력하는 문제임..

문제 링크 : www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 2차원 배열 형태의 입력에서 목적지까지의 최대 가치를 구하는 문제이다. 문제에서 로봇은 위쪽으로 이동할 수 없다는 것에 주목하자. 로봇이 위쪽으로 이동할 수 없기 때문에, 어떤 한 행에 대한 최대 가치를 구하기 위해 그 이전 행의 최대 가치들을 미리 구해놓는다는 접근이 가능하다. 또한 로봇은 오른쪽, 왼쪽 양방향으로 이동 가능하며, 한번 지난 칸은 이동할 수 없다는 제약을 갖고 있다. 이..