| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 2117 | 799 | 635 | 38.602% |
문제
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.
입력
첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치는 0이 아니며, 그 절댓값이 10,000보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
접근
이 문제에서 생각해야 될 것은 크게 세 가지다.
첫 번째는, 오른쪽(+)과 왼쪽(-)을 분할할 것.
두 번째는, 절댓값이 가장 큰 수를 제일 마지막에 방문할 것.
세 번째는, 최대 수인 M개의 책을 들고 가는 것은 이왕이면 먼 곳으로.
이 부분만 고려하면 쉽게 풀 수 있다.
풀이
L와 R이란 벡터를 만들어, 부호에 따라 다르게 관리하였다.
각 절댓값이 큰 수부터 정렬하여, 멀리 있는 위치 먼저 이동하면서, 인덱스를 M개씩 이동하였다.
마지막으로 방문하는 수는, L과 R의 첫번째 인덱스 중 절댓값이 더 큰 곳을 빼주었다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, ans = 0, height[10000];
pair<int, pair<int, int>> arr[100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
MS(height, 0);
CIN(N);
FUP(i, 0, N - 1)
{
CIN3(arr[i].first, arr[i].second.first, arr[i].second.second);
}
sort(arr, arr + N);
FUP(i, 0, N - 1)
{
int y = arr[i].first;
int left = arr[i].second.first;
int right = arr[i].second.second;
ans += (y - height[left]);
ans += (y - height[right - 1]);
FUP(h, left, right - 1) height[h] = y;
}
COUT(ans);
return 0;
}
Beginner