[BOJ][실3][1449] 수리공 항승

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

물이 세는 곳이 1,2,3이고 테이프 길이가 1일 때 각 지점에 1개씩 3개가 필요합니다. 테이프 길이가 2일 때는 1에서부터 붙히면 1,2는 커버되고 3은 새롭게 하나 붙여야 합니다.

붙이기 시작하는 지점을 start라고할 때, start+L-1만큼 커버할 수 있습니다. 테이프를 어디서 붙이기 시작했는지 start에 저장해두고, 새롭게 테이프를 붙여야할 때마다 start를 갱신합니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1010;

int n, m, k;
int arr[MAX];
int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(arr, arr + n);
  int ans = 1;
  int start = arr[0];
  for (int i = 1; i < n; i++) {
    int cover = start + m - 1;
    if (cover < arr[i]) start = arr[i], ans++;
  }
  cout << ans;
  return 0;
}

Success Notice: 수고하셨습니다.