문제 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) ..

문제 https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 짝수와 홀수로 두 집합을 만들어 이분 매칭으로 해결하는 문제. 이분 매칭을 잘 모른다면 다음 기본 문제를 먼저 해결해보고 오자. [백준] No.2188 - 축사 배정 (C++, 이분 매칭) 두 자연수를 더하는 경우는 3가지로 분류할 수 있다. 1. 짝수 + 짝수 짝수끼리 더한 수는 짝수이기 때문..

문제 https://www.acmicpc.net/problem/9577 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 두 집합의 대응 관계를 해결하는 이분 매칭 문제. 기본 적인 이분 매칭 문제를 해결하고 오면 이해하기 쉬울 것이다. [백준] 축사 배정(2188) 이번 문제에서 두 집합으로 선택되는 것은 시간(A set)과 조각(B set)이다. 파일이 어떤 시더에게 있는지는 상관없이, 접속 시간에 해당 파일을 다운로드할 수 있는 여부가 중요하기 때문이다. 따라서 시더..

문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 이분 매칭 문제들은 최대 유량을 이용하면 간단히 해결할 수 있다. [네트워크 유량] Network Flow(최대 유량, 최소 컷) 알고리즘 이분 매칭 문제는 두 집합에서의 대응 관계를 해결할 수 있다. 대표적으로 작업 배분을 한다고 생각해보자. A집합(인원)이 할 수 있는 B집합(작업)들 중 하나 선택하여 배정받는다. 이때 최대한의 작업을 할 수..