BOJ/백준 - 1449 수리공 항승 C++

처음에는 이제.. 내림차순으로 정렬하고 뺀 결과만큼 붙이는걸로 풀었었다.

근데 이제 그 생각은 실패를 곁들인..

 

간단히 생각해서 풀면 되는 문제였다.

1. 오름차순으로 정렬한다

2. 테이프의 길이만큼 테이프를 붙인다.

 

2번의 과정을 v.size()만큼 반복하는데, 대신 fix배열을 선언하여 붙였는지 안붙였는지 표시하면 된다.

만약에 현재 위치(pos)에서 테이프를 붙이지 않았다면 테이프 길이만큼 붙이면 된다.

문제에서 겹쳐도 된다고 했는데 굳이 그럴 필요는 없다 왜냐면 일단 길게 붙여야 최솟값을 만들 수 있으니까

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, L;
vector<int> v;
int fix[1001];
int answer = 0;
 
int main(void) {
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin >>N >> L;
 
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
 
 
    for (int i = 0; i < v.size(); i++) {
        int pos = v[i];
 
        if (fix[pos]==0) {
            for (int j = pos; j < pos+L; j++) {
                if (j > 1000) break;
                fix[j] = 1;
            }
            answer++;
        }
    }
 
    cout << answer;
    return 0;
}