문제

링크

풀이

(뒷일은 생각하지 않고) 앞에서 부터 붙여야 하는 위치에 테이프를 붙여주는 단순한 문제이다. 👉 그리디 알고리즘

주의해야 할 점 : 붙여야 하는 위치가 순서대로 입력된다는 조건이 없으므로 sort를 해줘야 한다.

🔥trouble shooting

1. 처음에는 물이 새는 곳의 좌표를 순서대로 돌면서 인접한 좌표의 사이 길이만큼 붙여야 할 테이프의 개수를 세어줬지만 좀 복잡한 접근이었다.

차라리 가상의 좌표를 만들어 테이프 붙인 곳을 표시해주는 방법이 간단했다.

2. 예제대로 잘 출력도 되고 반례도 없는것 같은데 계속 틀린답이라고 채점되었다. 이것저것 시도해보니 물이 새는 곳의 좌표를 담을 배열을 선언할때 N으로 했었는데 아에 max값인 1001로 해주니 정답으로 채점되었다.

배열 선언시 그럴 필요 없어보여도 넉넉하게 해주자..그럴 필요 있더라..

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, L, cnt = 0;
    cin >> N >> L;
    int position[1001]; // 물이 새는 곳의 좌표

    for (int i = 0; i < N; i++)
    {
        cin >> position[i];
    }

    sort(position, position + N);

    // 가상의 좌표를 만들어 테이프 붙인곳 표시
    bool coord_tape[1001];

    for (int i = 0; i < N; i++)
    {
        if (coord_tape[position[i]] == false) // 물이 새는 곳에 테이프가 안붙어있는 경우
        { 
            for (int j = position[i]; j < position[i] + L; j++)
            {
                coord_tape[j] = true;
            }
            cnt++;
        }
    }

    cout << cnt << "\n";

    return 0;
}