반응형 그리디16 프로그래머스 요격 시스템 - C++ 풀이 1. 타겟들을 끝점 기준으로 오름차순 정렬한다. 2. 순차적으로 끝점에서 요격한다. 3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다. 1. 타겟들을 끝점 기준으로 오름차순 정렬한다. 먼저 타겟들을 끝점 기준으로 오름차순 정렬한다. 끝점의 x좌표가 작은 순서대로 처리하기 위함이다. 2. 순차적으로 끝점에서 요격한다. 요격 횟수를 최소화해야 하므로 한 번의 요격으로 최대한 많은 타겟을 처리해야 한다. 따라서 타겟의 최대한 끝점에서 요격해야 뒤에 있는 타겟들에 최대한 많이 걸칠 수 있다. 마지막 요격점은 기록해둔다. 3. 만약 현재 타겟의 (시작점 > 마지막 요격점)인 경우, 새로 요격해야 한다. 만약 현재 타겟의 시작점이 마지막 요격점보다 뒤에 있는 경우 요격 포인트안에 들어.. 2023. 9. 4. 프로그래머스 택배 배달과 수거하기 - C++ 풀이 1. 배달은 갈 때, 수거는 돌아올 때 한다. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다. 1. 배달은 갈 때, 수거는 돌아올 때 한다. 이동 거리를 최소화해야 한다. 물류센터에서 출발할 때 트럭을 배달상자로 가득 채우고 출발한다. 가면서 각 집에 상자를 배달하여 트럭을 비우고, 다시 물류센터로 돌아오면서 수거상자들로 트럭을 채워오자. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 또한 이동 거리를 최소화하기 위해서는 최대한 먼 집부터 방문하는 것이 최적이다. (A= 0 || pp >= 0) { int dist = 0; // 트럭을 배달상자로 채움 truck = cap; // 배달은 갈 때 while (truck > 0 && dp >=.. 2023. 7. 22. 백준 13305번 주유소 - C++ 풀이 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다. #include using namespace .. 2022. 9. 27. 백준 4716번 풍선 - C++ 풀이 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. A 풍선과 B 풍선의 합은 항상 K로 유지되어야 한다. 따라서 풍선이 모자라서 더 먼 곳을 택해야할 때 생기는 손해가 가장 큰 팀에게 먼저 풍선을 배부해서 손해를 줄여야 한다. 즉, | DA-DB | 값 내림차순으로 정렬한 뒤, 각 팀의 이동 거리가 최소가 되도록 배부해준다. #include #include #include using namespace std; typedef long long ll; struct Team { int k, da, db; }; int N, A, B; vector teams; bool cmp(const Team& lhs, const Team& rhs) { return ab.. 2022. 9. 3. 백준 1744번 수 묶기 - C++ 풀이 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 3. n+1 > n*1이므로 1은 항상 묶지 않고, 0은 음수랑만 묶는다. 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 양수와 음수를 묶으면 음수가 되어 묶지 않고 그냥 더하는 것보다 합이 더 작아진다. 따라서 양수는 양수끼리, 음수는 음수끼리만 묶도록 한다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 이때 합이 최대가 되려면 절댓값이 큰 수부터 차례로 묶어야 한다. 만약 숫자가 홀수개라 마지막 수가 남는다면 그냥 더해준다. 3. n+1 > n*1이므로 1은 항상 묶지 않고.. 2022. 8. 26. 이전 1 2 3 4 다음 반응형
