c언어 2170번 선 긋기 (백준)

#include <stdio.h>

int main(void)
{
	int n = 0; //입력
	int tmp = -1;
	scanf("%d", &n);
	long long int a[n][2];
	while(++tmp < n) scanf("%lld %lld", &a[tmp][0], &a[tmp][1]);
	
	int key0, key1, i, j; //shell sort
	int gap = n/2;
	while(1) {
		if(gap%2==0) gap++;
		for(i = gap; i<n; i++) {
			key0 = a[i][0];
			key1 = a[i][1];
			for(j = i-gap; j>=0; j-=gap) {
				if(key0 < a[j][0]) {
					a[j+gap][0] = a[j][0];
					a[j+gap][1] = a[j][1];
				} else break;
			}
			a[j+gap][0] = key0;
			a[j+gap][1] = key1;
		}
		if(gap == 1) break;
		gap /=2;
	}
	
	long long int sum = 0; //sweeping
	long long int left = 0;
	long long int right = 0;
	int first = 0;
	for(int i = 0; i<n; i++) {
		if(first == 0) {
			left = a[i][0];
			right = a[i][1];
			first++;
		} else {
			if(right < a[i][0]) {
				sum += right-left;
				left = a[i][0];
				right = a[i][1];
			} else {
				if(right < a[i][1]) right = a[i][1];
			}
		}
		printf("%lld %lld\n",left, right);
	} sum += right - left;
	printf("%lld", sum); //출력
}

 

풀이 : 왼쪽을 기준으로 정렬, sweeping

1. 왼쪽을 기준으로 정렬 

2.  sweeping

2-1) 처음 것은 초기값으로

2-2) 초기값보다 왼쪽 값이 같거나 작으면, 두 선은 결합된다

2-3) 초기값보다 왼쪽값이 더 크면, 두 선은 떨어져 있다 -> 선의 길이를 누적하고, 초기값을 수정한다.

 

범위가 너무 커서 (20억) 배열로 하기엔 용량도 크고 시간도 너무나 오래 걸린다.

 

 

https://www.acmicpc.net/problem/2170

2170번: 선 긋기