[틀림] 프로그래머스 기지국 설치 // 그리디, 엣지케이스, 수학

https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=cpp

프로그래머스

 

풀이

N이 2억이기때문에, 완탐, dp는 불가능 합니다.

그리디, 수학적으로 풀어야 합니다.

prev를 마지막의 커버된 아파트의 위치로 정의합니다.

w가 주어지면, 2*w+1의 범위는 커버가 가능한것은 추론했음.

(station - w -1 ) -prev로 a구간의 길이를 구함

구간을 하나하나 보지않고 숫자 뺄셈연산으로 한번에 처리한것이 키포인트.

a구간을 2*w+1로 나누고, 올림하면 필요한 기지국의 갯수가 됨.

 

엣지케이스

엣지케이스를 생각안하면 틀리는 문제

기지국 뒤가 남는경우, a를 새로구하고 정답에 더해줘야함

기지국이 처음에 있는경우, station - w -1이 음수가됨, 음수나눗셈이 되어 c++의 if문은 0일때만 거짓을 반환하므로, 의도치않게 정답에 더해짐 -> a가 음수인경우 pass && prev만 갱신 하도록 수정필요

 

정답코드

#include <bits/stdc++.h>

using namespace std;

int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    int prev = 0; // 마지막으로 커버된 아파트의 위치

    for(auto station : stations){
        int a = (station - w - 1) - prev; // 앞 구간의 미커버 아파트 수
        if(a > 0){  // 미커버 구간이 있을 때만 계산
            int b = a / (2*w + 1);
            if(a % (2*w + 1)) b++;
            answer += b;
        }
        prev = station + w;
    }
    
    // 마지막에 남은게 없는경우, 추가계산 불필요
    if(prev>=n) return answer;
    
    int a = n - prev;
    int b = a / (2*w + 1);
    if(a % (2*w + 1)) b++;
    answer += b;
    
    return answer;
}