본문 바로가기

백준

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 고양이와 개가 나오는 티비쇼가 있고 사람들이 투표를 한다. 투표가 반영이 되면 시청자로 남고 반영이 안되면 시청을 그만둔다. 쇼 제작자는 시청자를 최대로 유지하고 싶다. 문제를 다른 시각으로 보기 사람들 (혹은 플레이어, 참여자) 사이에 의견이 있다. 두 사람 사이의 의견에 충돌이 있으면, 두 사람도 만족을 하는 결과는 없다. 최소한 둘 중 하나는 결과에 불만족 하게 된다. (둘 다 될 수도 있다.) 이 문제를 그래프로 모델링 하기 위해 사람을 그래프를 구성하는 정점으로 볼 수 있다. 두 사람 사이의 의견 충돌이 있으면, 두 사람 사이에 간선을 추가 해서 의견 충돌을 모델링 할 수 있다. 그럼 이 문제는 서로 의견이 대립되지 않는 사람의 .. 더보기

티스토리툴바