BOJ 2459 철사 자르기


사용한 알고리즘

  • 구현

알고리즘 설명

  • 시작점 부터 잘리기 전까지 철사 길이를 더한다
  • 잘린뒤에는 다음에 잘리기 전까지 더한다
  • 이렇게 모든 철사의 길이를 각각 구하면서 최대 길이면 남겨둔다.
  • 결과를 출력한다.

풀이

// 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;
}



© 2020.08. by fbdp1202

Powered by theorydb