본문 바로가기

problem solving

BOJ 16074 Mountaineers (병렬 이분 탐색) https://www.acmicpc.net/problem/16074 16074번: Mountaineers The Chilean Andes have become increasingly popular as a destination for backpacking and hiking. Many parts of the Andes are quite remote and thus dangerous. Because of this, the Ministry of Tourism wants to help travelers plan their trips. In particular, t www.acmicpc.net 지형이 주어지고, 어느 두 지점을 이동하는 경로 중 경로상 최고 고도를 최소화하는 문제이다. 쿼리의 개수가 5만개 이므.. 더보기
BOJ 12771 Oil (ACM-ICPC 2016 WF) https://www.acmicpc.net/problem/12771 12771번: Oil The first line of input contains a single integer n (1 ≤ n ≤ 2 000), which is the number of oil deposits. This is followed by n lines, each describing a single deposit. These lines contain three integers x0, x1, and y giving the deposit’s position as www.acmicpc.net 직선을 하나 그어, x 축에 수평한 선분을 최대한 많이 지나가게 만드는 문제이다. (지나가는 선분의 합을 최대화) 직선이 선분의 끝에 닿아도 지나.. 더보기
BOJ 12766 지사 배정 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/12766 12766번: 지사 배정 입력의 첫줄은 4개의 정수 n, b, s, 그리고 r로 이루어진다. n (2 ≤ n ≤ 5 000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50 000)은 도로의 수를 www.acmicpc.net 방향그래프의 정점에 위치한 그래프들을 S개의 그룹으로 묶어, 한 그룹내에서 모든 지사들 사이에서 통신을 할 때, 총 통신비용을 최적화 하는 문제이다. 두 지사 사이의 통신은 항상 본부를 거쳐서 지나가야 한다. 따라서 본부 s에서 지사 u까지의 거리 D[s][u], 그리고 지사 u에서 본부 s까지의 거리를 D[u][s] 라고 하면.. 더보기
BOJ 5466 상인 (IOI 2009 Salesman) https://www.acmicpc.net/problem/5466 5466번: 상인 어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부 www.acmicpc.net 문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합. DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기. 위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면, 우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 .. 더보기
BOJ 17399 트리의 외심 https://www.acmicpc.net/problem/17399 17399번: 트리의 외심 첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다. 두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 www.acmicpc.net 일단 각 쿼리에 대해 트리에서 최소 공통 조상(Lowest Common Ancestor)을 log n에 구할 수 있어야 한다. 알고리즘 두 정점 a와 b에 대해, 두 정점의 가운데에 위치한 정점 x를 찾는다. a와 b 거리가 짝수여야 한다. 그렇지 않으면 가운데에 위치한 정점을 정의할 수 없다. 단계 1에서 찾은 정점 x로부터 정점 c까지의 거리를 구한다. x.. 더보기
BOJ 13261 탈옥 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/13261 13261번: 탈옥 한 간수가 1, 2, 3번 방을, 다른 간수가 4, 5번 방을, 다른 간수가 6번 방을 감시한다고 하면 탈옥 위험도가 최소가 된다. 1, 2, 3번 방을 감시하는 간수는 총 3명의 죄수를 감시하고 있기 때문에, 1, 2, www.acmicpc.net 컨벡스 홀 최적화 각인줄 알고 식 유도하려고 뻘짓하다가 알고 보니 너무 당연하게 분할정복 최적화였던 문제. 분할정복 최적화를 적용할 수 있는 케이스는 아래와 같다. 점화식: DP[i][j] = min { DP[i-1][k] + C[k][j] } ( k < j ) C[k][j] 는 monge array C[a][c] + C[b][d] 더보기
BOJ 10350 은행 (IMO 1986) https://www.acmicpc.net/problem/10350 10350번: 은행 월 스트리트에는 n개의 은행이 있다. 모든 은행은 양 옆으로 이웃하는 은행이 하나씩 있으며, 첫 번째 은행의 왼쪽에는 마지막 은행이 있고, 마지막 은행의 오른쪽에는 첫 번째 은행이 있다(즉, www.acmicpc.net 지금 까지 풀어본 문제 중 체감 난이도가 가장 어려운 문제 중 하나이다. 1986년 국제수학올림피아드 (IMO 1986) 3번 문제의 일반화 버전으로, 당장 IMO 1986에서도 3번 문제가 가장 어려웠다는 평가가 있다. 그런 문제의 일반화 버전이니 문제의 난이도는 더 말할 필요가 없다. SEERC 2014의 A번 문제로도 출제되었다. (이 문제가 A라고?!). 대회 사이트에서 테스트 인풋 아웃풋을 받.. 더보기
BOJ 13972 파일합치기2 (크누스 최적화) https://www.acmicpc.net/problem/13974 13974번: 파일 합치기 2 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net dp[i][j] = i번 파일부터 j번 파일까지 합치는데 필요한 최소 비용이라고 정의하고, s[i][j] = i번 파일부터 j번 파일까지 파일 크기의 합이라 하면, 아래의 dp 점화식을 얻을 수 있다. dp[i][j] = min(i 더보기
BOJ 8872 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000 www.acmicpc.net 이 문제는 아래의 세 가지 경우로 나누어 생각할 수 있다. 1. Forest에 트리가 한 개인 경우 -> 그 트리의 지름 2. Forest에 트리가 두 개 이상인 경우 -> 그리디 해법: 반지름이 가장 큰 트리의 중심 정점에 다른 모든 트리의 중심 정점을 연결하는 게 최적이다. a. 반지름이 가장 큰 트리와 두 번째로 반지름이 큰 트리를 연결한 .. 더보기
BOJ 3683 고양이와 개 https://www.acmicpc.net/problem/3683 고양이와 개가 나오는 티비쇼가 있고 사람들이 투표를 한다. 투표가 반영이 되면 시청자로 남고 반영이 안되면 시청을 그만둔다. 쇼 제작자는 시청자를 최대로 유지하고 싶다. 문제를 다른 시각으로 보기 사람들 (혹은 플레이어, 참여자) 사이에 의견이 있다. 두 사람 사이의 의견에 충돌이 있으면, 두 사람도 만족을 하는 결과는 없다. 최소한 둘 중 하나는 결과에 불만족 하게 된다. (둘 다 될 수도 있다.) 이 문제를 그래프로 모델링 하기 위해 사람을 그래프를 구성하는 정점으로 볼 수 있다. 두 사람 사이의 의견 충돌이 있으면, 두 사람 사이에 간선을 추가 해서 의견 충돌을 모델링 할 수 있다. 그럼 이 문제는 서로 의견이 대립되지 않는 사람의 .. 더보기

티스토리툴바