[C++] 백준 1449번 수리공 항승

 

1) 문제설명

백준 Online Judge 1449번 수리공 항승

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

1449번: 수리공 항승

 

2) 아이디어

입력받은 배열을 오름차순으로 정렬하고 앞에서 뒤를 뺀 결과만큼 테이프를 소모한다.

그리고 테이프를 모두 소모하면(테이프의 길이가 1보다 작을 경우) 테이프를 다시 리셋시켜준다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
	int n, l;
	int* arr;
	cin >> n >> l;
	arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n); // 오름차순
	int cnt = 0, temp = l;
	int i = 0;
	while (i < n) { // 
		if (i + 1 < n) {
			l = l - (arr[i + 1] - arr[i]); // 테이프를 길이만큼 사용하다가
		}	
		if (l < 1) { // 테이프의 길이가 1보다 작으면
			l = temp; // 테이프의 길이를 초기화한다.
			cnt++;
		}
		i++;
	}
	cout << cnt+1 << endl;

}