본문 바로가기

boj

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] 더보기

티스토리툴바