반응형 정렬8 프로그래머스 과제 진행하기 - C++ 풀이 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 3. 다음과제를 시작하기 전까지 텀이 존재하는 경우, 텀 동안 중단했던 과제들을 해결한다. 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 시작시간에 맞춰 순차적으로 시작해야하므로, 시작시간을 기준으로 오름차순 정렬해둔다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 만약 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단해야 한다. 이때 중단된 과제들은 스택에 넣어둔다. 멈춰둔 과제가 여러 개일 경우.. 2023. 9. 5. 백준 10800번 컬러볼 - C++ 풀이 1. 공들을 크기 오름차순으로 정렬한다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) 1. 공들을 크기 오름차순으로 정렬한다. 먼저 공들을 크기 기준으로 오름차순 정렬해준다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합.. 2022. 10. 5. 백준 2170번 선 긋기 - C++ 풀이 1. 선분들을 시작점 오름차순으로 정렬한다. 2. 스위핑하면서 모든 선분의 길이를 더한다. 1. 선분들을 시작점 오름차순으로 정렬한다. 스위핑을 통해 해결할 수 있는 문제이다. 왼쪽부터 스위핑하면서 선분의 총 길이를 계산해줄 것이다. 이 작업을 위해 먼저 주어진 선분들을 시작점 오름차순으로 정렬한다. 2. 스위핑하면서 모든 선분의 길이를 더한다. 이제 왼쪽부터 스위핑하면서 모든 선분의 길이를 더한다. 중간에 겹치는 선분들을 하나의 선분으로 만들어주면서 이동해주면 된다. 현재 처리중인 선분의 시작점과 끝점 좌표를 각각 s, e, 다음 선분의 시작점과 끝점 과표를 각각 ns, ne라고 하자. 시작점 오름차순으로 정렬해주었기 때문에 s ≤ ns임은 보장되어 있다. 따라서 ns < e 이면, 현재 선분과 다음 .. 2022. 9. 15. 백준 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 다음 반응형
