1일1알

가격을 기준으로 내림차순으로 정렬한 뒤 투 포인터를 이용해 가격의 차이가 D 이상이면 왼쪽 포인터를 늘리고 아니라면 오른쪽 포인터를 늘리는 방식으로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; bool compare(const pair& lhs, const pair& rhs) { return lhs.first > rhs.first; } int main() { ios_base::sync_with_stdio(false); cin.tie..

1. 도착지점을 기준으로 오름차순 정렬을 한다. 도착지점이 같을 경우에는 시작지점을 기준으로 오름차순 정렬을 한다. (시작지점을 기준으로 정렬을 하면 독점이 일어날 수 있다.) 2. 각 지점마다 트럭의 용량을 저장하는 벡터를 만들고, 시작지점에서 도착지점까지 중 가장 트럭에 짐이 많이 실린 용량 을 찾는다. 3. 트럭의 짐의 용량 + 내 용량이 c보다 크면 짐을 실을 수 있는 만큼만 자른다. 4. 시작지점부터 도착지점까지 내 짐의 무게가 트럭에 더해진다. 5. 2~4를 m만큼 반복한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using ..

1. 배열을 탐색하면서 가장 큰 값을 찾는데, 순회 도중 인덱스가 s를 넘어가면 탐색을 중지한다. (인덱스가 s를 넘어서는 가장 큰 값을 찾았다고 해도 인덱스만큼 옮길 수 없기 때문에 그 수를 맨 앞으로 옮길 수 없다.) 2. 찾은 수는 맨 앞으로 옮길 수 있는 수 중에서 가장 큰 수이다. 맨 앞으로 옮기면 그 위치에 고정될 것이고, 앞으로 옮기는 데에 비용이 들기 때문에 배열에서 찾은 수를 지우고 새로운 벡터에 찾은 수를 넣는다. 3. 이론상으로는 앞으로 옮긴 것이기 때문에 s에서 찾은 수의 인덱스를 빼준다. 4. s가 0이 되거나 이미 모든 수가 정렬이 되어있으면 앞에서부터 차례대로 2에서 만든 벡터에 값을 넣어준다. 5. 새로운 벡터의 원소들을 출력한다. #include #include #inclu..

1. 크레인과 박스들을 내림차순으로 정렬한다. 2. 맨 앞의 박스가 크레인이 감당할 수 있는 무게보다 무거우면 옮길수 없으므로 1을 출력하고 프로그램을 종료한다. 3. 박스가 전부 빌 때까지 크레인을 순회하면서 박스를 순회하면서 (2중 for문) 박스를 담을 수 있으면 박스의 벡터에 erase를 통해 박스를 지워준다. (크레인 한 번 순회하면 cnt++) 위에처럼 풀어도 풀리긴 하지만 박스를 지우는 erase가 시간이 오래 걸린다. 크레인이 500개만 되어도 시간초과가 날 것이다. 그래서 erase를 사용하지 않고 visited를 이용해 이미 담은 것인지를 판별하도록 코드를 수정하였다. #include #include #include #include #include #include #include #in..

일반적인 정렬을 하면 첫 번째 원소와 마지막 원소를 비교했을 때 차이가 많이 나는 결과가 나오기 때문에 일반적인 정렬로는 해결할 수 없다. 정렬을 한 뒤 새로운 배열에 처음과 마지막 부분에 순서대로 삽입하는 방법을 생각해 볼 수 있다. 2, 4, 5, 7, 9 가 있으면 처음에 2, 마지막에 4, 다시 앞으로 와서 5, 다시 뒤로 가서 7, 다시 앞으로 와서 9 이런식으로 배열을 만들면 2, 5, 9, 7, 4 이렇게 만들어진다. 하지만 이런식으로 만들려면 배열을 하나 더 만들어야 하기도 하고 구현하기도 번거롭다. 그래서 위의 배열 2개에서 찾은 규칙이 있는데, 그 규칙으로 간단하게 문제를 해결할 수 있다. 정렬된 배열을 순서대로 앞뒤에다 배치하기 때문에 정렬된 배열의 특정 원소에서 2칸 떨어진 원소가 ..