시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1575 | 466 | 361 | 29.761% |
주택난을 해결하기 위해서 직선 도로 하나를 따라 여러 아파트 단지들을 지었다. 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 아파트 단지들이 서로 멀리 떨어져 있기 때문에 반드시 통학버스를 이용해서만 다닐 수 있고, 통학버스는 한 대이다.
각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 이 통학버스는 정원을 초과하여 학생을 태울 수 없고, 모든 학생을 등교시킬 때까지 이 과정을 반복한다.
위 규칙을 따라서 모든 학생들을 학교에 등교시키는 예를 보자. 아파트 단지 A, B, C가 각각 좌표 0, 2, 5에 있고 이 단지에 사는 학생은 각각 1, 2, 1명이라고 하자. 두 지점 간의 거리는 두 지점 좌표의 차이로 정의된다. 최대 4명이 탈 수 있는 통학버스가 좌표 4에 있는 학교에서 출발해서 모든 학생들을 등교시킬 때, 버스는 먼저 단지 B를 들러 2명을 태우고, 단지 A를 들러서 1명을 태우고 다시 학교로 돌아온다면 이동 거리는 2 + 2 + 4 = 8이다. 다시 학교에서 아파트 단지 C로 이동하여 1명을 태우고 돌아오면 이동 거리는 1 + 1 = 2가 되고, 총 이동거리는 8 + 2 = 10이 된다.
학교의 위치, 각각의 아파트 단지의 위치와 학생 수, 통학버스의 정원이 주어졌을 때, 모든 학생을 등교시키는데 필요한 통학버스의 총 이동 거리의 최솟값을 계산하는 프로그램을 작성하시오.
첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2<=N<=30,000이다. 두 번째 정수 K는 1<=K<=2,000이며, 통학버스의 정원이다. 세 번째 정수 S는 학교의 위치를 나타낸다. 둘째 줄부터 N+1번째 줄에는 각 아파트 단지의 위치를 나타내는 정수와 이 단지에 사는 학생 수를 나타내는 정수가 빈칸을 사이에 두고 주어진다. 학교와 아파트 단지의 좌표는 0 이상 100,000 이하이며, 이 좌표들은 모두 서로 다르다. 각 아파트 단지의 학생 수는 1 이상 2,000 이하이다.
첫째 줄에 주어진 입력에서 통학버스의 최소 이동 거리를 출력한다. 최소 이동 거리가 1,000,000,000을 초과하는 경우는 없다.
학교를 기준으로 가장 멀리 있는 아파트 단지 먼저 들리면 된다는 것은 바로 알 수 있다.
어떻게 구현하느냐의 문제인 것 같은데, 나는 왼쪽과 오른쪽을 나누었다.
그리고 매 순간 가장 멀리 있는 아파트 먼저 들려서 학생들을 태웠다.
우선 apart의 좌표를 기준으로 sort했다.
그리고, 제일 가까운 왼쪽 좌표의 인덱스를 mid로 놓고 찾았다.
이후 idx를 선언해 0부터 mid까지 확인하면서 ans에 왼쪽 먼 좌표의 값을 더했고,
마찬가지로 N - 1부터 mid + 1까지 확인하면서 ans에 오른쪽 먼 좌표의 값을 더했다.
#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, K, S, ans = 0;
pair<int, int> apart[30000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN3(N, K, S);
FUP(i, 0, N - 1) CIN2(apart[i].first, apart[i].second);
sort(apart, apart + N);
int mid = N - 1;
FUP(i, 0, N - 1)
{
if (S < apart[i].first)
{
mid = i - 1;
break;
}
}
if (mid != -1) // 왼쪽
{
int idx = 0;
while (idx <= mid)
{
int first = apart[idx].first;
int remain = K;
while (idx <= mid)
{
if (apart[idx].second > remain)
{
apart[idx].second -= remain;
break;
}
remain -= apart[idx++].second;
}
ans += (2 * (S - first));
}
}
if (mid != N - 1) // 오른쪽
{
int idx = N - 1;
while (idx > mid)
{
int first = apart[idx].first;
int remain = K;
while (idx > mid)
{
if (apart[idx].second > remain)
{
apart[idx].second -= remain;
break;
}
remain -= apart[idx--].second;
}
ans += (2 * (first - S));
}
}
COUT(ans);
return 0;
}