4Legs_Archives

문제 링크 : www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제를 간단하게 생각해야 깔끔하게 점화식을 구할 수 있다. "dp[k] = k일째 되는 날의 짚신벌레 개체 수"로 두고 문제를 풀어보자. 우선, 예제인 a = 2인 상황에서 짚신벌레가 증식만 한다고 가정한다면 다음과 같다. 0일째 되는 날: (0) 1일째 되는 날: (1) 2일째 되는 날: (2, 0) 3일째 되는 날: (3, 1, 0) 4일 째 되는 날: (4, 2, 1, 0, 0) 5일 째 되는 날: (5, 3, 2, 1, 1..

문제 링크 : 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 콤보에서 처리한 경..

서론 다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다." 이 메신저 프로그램을 통해 내가 A라는 사람과 친구 관계를 맺었다. 다음과 같은 관계도에서, 내가 주황색으로 표시된 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 위처럼 친구 관계를 그래프로 나타낸 후 나를 시작으로 그래프 탐색(DFS, BFS)을 통해 목표 정점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 새로운 친구 관계는 언제나 생겨날 수 있다. 만약 주황색으로 표시된 친구 관계가 새로 생겼다고 할 때, 우리는 주황색 사람과 친구 관계가 될 수 있는지 알기 위해서다시 그래프 탐색을 진행해야 한다. 하지만 이 메신저 프로그램을 사용하는 사용자의..

문제 링크 : 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' 에 주목하자. 이 조건을 이용하면 우리는 두 열..