devbelly

문제 https://www.acmicpc.net/problem/1398 알고리즘 DP, Greedy 풀이 최소 동전의 수를 묻는 문제입니다. 주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다. (1 10 25), (100 1000 2500), (10000 100000 ...) 즉 DP를 100씩 끊어서 사용하면 됩니다. 코드 #include ..

문제 https://www.acmicpc.net/problem/5832 알고리즘 Greedy 풀이 겹치는 선분이 있을 때, 해당 구간을 잘라 그리디하게 푸는 문제입니다. $K$ 쌍을 입력받고 선분의 끝점 값을 기준으로 정렬합니다. 현재 보고 있는 선분의 구간이 [u,v] 일 때, 선분들 중 시작점에 있는 값이 v보다 작다면 겹치는 구간이 발생하는 선분입니다. 해당 선분들은 [u,v] 구간을 자를 때 같이 해결이 되므로 $visited$배열을 통해 체크하며 답을 찾으면 쉽게 풀 수 있습니다. $K$쌍이 주어질 때 u>v 일 수도 있으니 u>v라면 swap을 통해 시작점 N >> K; rep(i, K) { int u, v; cin >> u >> v; if (u > v) swap(u, v); vt.emplac..

문제 https://www.acmicpc.net/problem/5872 알고리즘 Greedy 풀이 올바른 괄호문자열을 만들기 위해 몇 개의 문자를 추가해야하는지에 대한 문제와 거의 비슷합니다. 괄호 하나를 뒤집는 것은 두 개의 문자를 추가하는 것과 일치합니다. 왼쪽부터 문자열을 검사하며 만일 닫는 괄호가 더 많아지는 순간에는 바로 해당 괄호를 여는 괄호로 바꿉니다. 문자열 끝까지 검사한 후 괄호쌍이 맞지 않다면 $sum$만큼의 닫는 괄호를 추가해주면 해결가능합니다. 이는 $sum/2$ 횟수만큼 괄호를 뒤집는 것과 일치합니다. 코드 #include #define rep(i, n) for (int i = 0; i s; in..

문제 https://www.acmicpc.net/problem/8980 알고리즘 Greedy 풀이 1부터 N까지 트럭이 이동하며 배송을 할 때, 최대 배송량을 구하는 문제입니다. 1마을에서 모든 택배를 들고 있을 때, 포기 해야하는 택배는 1마을로부터 가장 먼 택배들입니다. 이 택배는 오래 들고 있을수록 중간마을에서의 배송을 방해하기 때문입니다. 도착마을을 기준으로 오름차순으로 정렬하여 다른 택배들에게 영향을 덜 주는 순서대로 처리해나가면 풀 수 있습니다. 영향을 준다는 것은 현재 처리하고 있는 택배의 도착지가 다른 택배들의 시작점과 도착점 사이에 있다는 것인데 도착마을을 기준으로 오름차순 정렬하면 이와 같은 일이 최소화 됩니다. 코드 #include #define rep(i, n) for (int i ..

문제 https://www.acmicpc.net/problem/2437 알고리즘 Greedy 풀이 $N$개의 저울이 주어졌을 때, 잴 수 없는 무게의 최솟값을 구하는 문제입니다. 기존에 잴 수 있는 구간이 [0,R] 일 때, 새로운 추 A가 새로이 등장하면 새롭게 잴 수 있는 구간은 [A,A+R] 일 것입니다. 만일 R+1>=A 라면 이 구간은 [0,A+R]로 통합되어 잴 수 있는 구간이 새로이 갱신되겠지만 아니라면 답은 R+1입니다. 즉, 추의 무게를 정렬한 후 R과 추가할 추 A의 무게를 계속해서 비교해주면 됩니다. R은 잴 수 있는 무게의 최댓값이므로 지금까지의 추의 무게의 총합입니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #defi..

문제 https://www.acmicpc.net/problem/9869 알고리즘 Greedy 풀이 소마다 우유생산량과 수명이 주어질 때, 최대 우유생산량을 구하는 문제입니다. 자주 보이는 그리디 테크닉입니다. 시간을 0부터 접근하는 대신, 가장 마지막 시간부터 0까지 역순으로 소들을 고려합니다. T에 해당하는 시간에 젖을 짤 수 있는 소들을 PQ에 넣습니다. 이렇게 하면 현재 젖을 짤 수 있는 소들이 PQ에 담기게 됩니다. 이 가운데 우유 생산량이 높은 소부터 젖을 짜나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; vector vt; rep(i, N) { int..

문제 www.acmicpc.net/problem/6068 알고리즘 Greedy 풀이 일을 처리하는데 걸리는 시간, 일의 마감기한이 주어졌을 때 일을 시작해야하는 가장 늦은 시간을 구하는 문제입니다. 일을 마감기한에 딱 맞춰서 끝내는 것이 일을 가장 늦게 시작할 수 있을 것입니다. 마감기한이 가장 늦은 일부터 마감시간에 딱 맞게 일을 역순으로 처리해나가며 현재시간과 다음으로 처리해야할 일의 마감기한중 작은 값을 현재시간으로 취해나가며 시뮬레이션 하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int a, b; cin >> a >> b; vt.e..

문제 www.acmicpc.net/problem/4716 알고리즘 greedy 풀이 방 A, B에 풍선이 있고 각 팀마다 방마다의 거리와 얻을 풍선수가 주어질 때 최소로 이동하는 거리를 구하는 문제입니다. 이 문제의 답을 가장 방해(?)하는 것은 방과의 거리가 먼 팀입니다. 답을 최소로 만들어야하는데 먼 거리를 통해 해당 팀에 풍선을 전달하면 답을 찾기가 어려워집니다. 입력 예제에서 3번팀은 각 방과의 거리가 40과 10입니다. 거리가 10인 방을 이용해서 풍선을 전달해야 거리가 40인 방의 풍선을 전달받지 않아 최소로 답을 구할 수 있을 것입니다. 그렇다면 우선적으로 고려해야할 것은 방과의 거리가 먼 팀일까요? 비슷하긴 하지만 답은 아닙니다. A방에서 가져올 풍선을 B방을 선택해서 이득을 보거나 B방에..