문제 https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 A(상덕이)가 부른 마지막 음을 a, B(희원이)가 부른 마지막 음을 b라고하자. dp[a][b]에는 a와 b일때의 힘든정도의 최솟값을 저장하자. 이때 현재까지 두 명이 부른 음은 a와 b 중에 더 큰 값(악보상에서 더 뒤에 있는 음)이라고 할 수 있다. (모든 음은 순서대로 불러야 하므로 이는 성립할 수밖에 없다.) 그렇다면 다음으로 불러야 ..

문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 연속된 순서의 파일끼리만 합쳐야 한다는 조건이 없다면 우선순위 큐로 간단히 풀 수 있지만, 연속된 파일끼리 합치기 위해 다이나믹 프로그래밍(DP)를 사용해야 한다. dp[start][end]를 start ~ end까지의 파일을 연속되게 합칠 때(하나의 임시 파일로 만들 때) 최소 비용이라고 하자. 이를 구하기 위해서는 start~end 파..

문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 자신의 직속 부하가 최고 상관인 서브 트리들에서의 최소 전파 시간을 구한 값을 배열에 저장한다 생각해보자. 부하의 서브 트리들 중에서 가장 전파 시간이 오래 걸리 트리는 언제 방문해야 최단 시간을 구할 수 있을까? 조금만 생각해보면 당연히 전파 시간이 오래 걸리는 순서대로 먼저 방문해야 항상 이득임을 알 수 있다. (오래 걸리는 트리를 늦게 방문할수록 ..

문제 https://www.acmicpc.net/problem/10251 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 참조 풀이 JusticeHui님의 백준10251 운전 면허 시험 풀이 언뜻 보면 최단 거리를 구하는 문제 같지만 사용할 수 있는 연료의 한계가 있기 때문에 풀기 어려웠던 문제. 연료에 제한이 있으면 해당 경로가 최단 경로이라도 연료의 사용량이 많다면 결국에 이용을 못 할 수 있으므로 모든 경우의 수를 생각해보아야 한다. 이때 중요한 것이 모든 도로를 지나는데 걸리는 시간은 L로 동일하고, 방향을..

문제 https://www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 [백준] 고층 빌딩(1328) 문제와 완전히 동일한 풀이로 해결할 수 있다. dp[stick][l][r]를 stick 개수의 막대를 놓았을 때 왼쪽에서 l개, 오른쪽에서 r개가 보이는 경우의 수 라고하자. 모든 막대를 항상 가장 큰 막대부터 작은 막대의 순서대로 놓는다고 생각해보자. 지금까지 stick - 1개의 막대를 놓았다면 다음으로..

문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 풀이 solved.ac 난이도: Platium5 [백준] 평범한 배낭(12865)의 다음 단계 문제로 같은 물건이 여러 개 있는 경우이다. 이 문제를 일반적인 배낭(Knapsack) 문제와 동일하게 해결하려 시간 복잡도가 O(N* K *M)이기 때문에 시간 초과가 발생한다. 따라서 다음과 같은 최적화가 필요하다. 물건의 개수를 2의 제곱수의 합으로 분..

문제 https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 높이 순서로 정렬 후, 해당 그림이 선택될 수 있도록 하는 앞의 그림들 중 가장 높은 그림을 미리 저장해 두자. 이를 저장하는 이유는 다음과 같은 점화식을 구현하기 위해서 이다. dp[idx]를 idx번째 그림까지를 고려했을 때, 판매 가능한(선택된) 그림의 가격 합의 최대 값이라 고하자. dp[idx]를 구할 때 두 가지 경우를 고려해..

문제 https://algospot.com/judge/problem/read/PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 algospot.com 풀이 종만북 난이도: 중 일반적인 배낭 문제(Knapsack)에서 추가적으로 어떤 물건을 선택했는지까지 출력해야 하는 문제이다. 배낭 문제는 DP의 대표적인 문제로, 구현 방법에는 재귀 함수를 통해 큰 문제에서 작은 문제로 내려가며 해결하는 Top-Down 방식과 작은 문제에서부터 차례로 답을 찾아 올라가는 Bottom-Up방식이 있다. 이번 문제는 Bottom-Up..

문제 https://www.acmicpc.net/problem/2570 2570번: 비숍2 첫째 줄에 정사각형 체스판의 크기 N이 주어진다. 둘째 줄에는 체스판 위에 놓인 장애물의 개수 M이 주어진다. N은 100이하의 자연수이고 M은 음이 아닌 정수이다. 이어 셋째 줄부터 한 줄에 하나 www.acmicpc.net 풀이 solved.ac 난이도: Platium 2 이분할 집합에 대해 곰곰이 생각해봐야 풀 수 있는 이분 매칭 문제. 한 좌표에 비숍을 놓으면 해당 비숍에 의해 더 이상 다른 말을 놓을 수 없는 두 대각선이 생긴다. 하지만 좌표와 두 대각선을 이분 매칭을 진행하는 것은 불가능하다. (하나의 좌표에 대각선을 두 개 매칭해 주어야하기 때문에) 따라서 방향이 다른 대각선끼리 집합을 만들어 이분 매..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 [네트워크 유량] Network Flow(최대 유량) 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이 everenew.tistory.com 네트워크 유량, 최대유량 (Network Flow / Maximum Flow) ..