백준 1449 수리공 항승

작성일 | In |

Problem : 수리공 항승

유형 : 그리디

문제 해석

  • 테이프를 최소로 이용하여 물이 새는걸 막으시오

문제 재해석

  • 구멍난 곳에서 좌우로 0.5 만큼 붙여야 물이 새는걸 막을 수 있다.
  • 구멍은 크기가 따로 없다 항상 점의 형태로만 존재한다.

해결 전략

  • 순차적으로 앞에서 부터 테이프를 붙여나간다.
  • 구멍 좌 우측으로 0.5cm에 테이프가 붙어 있지 않다면, 테이프를 붙인다.

설계, 구현

  • 구멍의 좌,우측에 테이프가 붙어 있지 않다면, 해당 위치부터 테이프를 새로 붙여버린다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int n, tape_len, tape_cnt;
double cur;

int weak[1002];

void Solve() {
    for (int i = 0; i < n; ++i) {
		if (cur < double(weak[i] - 0.5)) {
			cur = weak[i] - 0.5 + tape_len;
			tape_cnt++;
		}
		if (cur < double(weak[i] + 0.5)) {
			cur = weak[i] + 0.5 + tape_len;
			tape_cnt++;
		}
    }
    cout << tape_cnt;
}

void Input() {
    cin >> n >> tape_len;
    for (int i = 0; i < n; ++i) {
        cin >> weak[i];
    }
    sort(weak, weak + n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 이런 쉬운 문제는 10분내에 구현까지 끝낼 수 있도록 사고를 빠르게하자.