사용한 알고리즘
알고리즘 설명
- 시작점 부터 잘리기 전까지 철사 길이를 더한다
- 잘린뒤에는 다음에 잘리기 전까지 더한다
- 이렇게 모든 철사의 길이를 각각 구하면서 최대 길이면 남겨둔다.
- 결과를 출력한다.
풀이
// baekjoon 2459 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAX_K=111111;
int N, K, I;
long long line[MAX_K], ans;
P point[MAX_K];
inline long long dist(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
scanf("%d%d", &N, &K);
for (int i=0; i<K; i++)
scanf("%d%d", &point[i].first, &point[i].second);
point[K].first = point[K].second = 1;
scanf("%d", &I);
int pos=0, cur_x=1, cur_y=1, i=0;
long long ret=0;
while (i<=K) {
// 현재 철사 모서리가 잘리는 지점보다 작은 경우
if (cur_x <= I) {
// 다음 철사 모서리도 잘리는 지점보다 작은 경우 철사길이 계속 유지
if (point[i].first <= I) {
ret += dist(point[i].first, point[i].second, cur_x, cur_y);
cur_x = point[i].first;
cur_y = point[i].second;
i++;
}
// 현재 철사 다음 철사 사이에 잘리게 되는 경우
else {
ret += dist(I, point[i].second, cur_x, cur_y) + 1;
ans = max(ans, ret);
line[pos++] = ret;
ret = dist(I+1, cur_y, point[i].first, cur_y);
cur_x = point[i].first;
cur_y = point[i].second;
i++;
}
}
// 현재 철사 모서리가 잘리는 지점보다 큰 경우
else {
// 현재 철사 다음 철사 사이에 잘리게 되는 경우
if (point[i].first <= I) {
ret += dist(I+1, point[i].second, cur_x, cur_y) + 1;
ans = max(ans, ret);
line[pos++] = ret;
ret = dist(I, cur_y, point[i].first, cur_y);
cur_x = point[i].first;
cur_y = point[i].second;
}
// 현재 철사와 다음 철사 사이가 잘리지 않는 경우
else {
ret += dist(point[i].first, point[i].second, cur_x, cur_y);
cur_x = point[i].first;
cur_y = point[i].second;
i++;
}
}
}
// 마지막 철사 지점으로 되돌아 오기 때문에 첫번째 라인에 더해줌
ans = max(ans, line[0]+ret);
printf("%lld\n", ans);
return 0;
}