[백준,c++] 1449번 - 수리공 항승

문제

1449번: 수리공 항승

 

코드

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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,L; cin>>N>>L;
    vector<int>v;
    for(int i=0; i<N; i++){
        int inp; cin>>inp;
        v.push_back(inp);
    }
    sort(v.begin(),v.end());
    double start = 0, end = 0, now = 0;
    int cnt = 0;
    for(int i=0; i<N; i++){
        start = v[i]-0.5;
        end = v[i]+0.5;
        if(now<end){
            if(now<start) now = start;
            int temp_cnt = (end - now) / L;
            if(temp_cnt==0) temp_cnt = 1;
            cnt += temp_cnt;
            now = start+ (L * temp_cnt);
        }
        
    }
    cout<<cnt;
    
}

 

풀이

문제에서 "승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다."라는 조건에 의해서 start = v[i] - 0.5, end = v[i] + 0.5로 지정해줍니다. 그리고 now는 현재 테이프의 위치를 뜻하는데 만약 현재 테이프 위치보다 end지점이 더 크다면 그만큼 테이프를 더 사용해야 한다는 것을 의미합니다. 그래서 필요한 만큼 테이프를 개수를 더하고, 현재 지점은 start +  테이프의 길이 * 테이프 개수의 값으로 갱신해줍니다. if(now<start) now = start;라는 조건을 준 이유는, 스타트 지점부터 테이프를 칠하면 되기에 불필요한 테이프칠을 하는 행위를 막기 위해 추가해주었습니다.