[프로그래머스/c++] Lv1 덧칠하기

https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

 

• section 배열 정렬: 이미 정렬되어 있다고 가정해도 좋지만, 혹시나 정렬이 안 되어 있다면 정렬이 필요함
• 그리디 접근: section에서 아직 페인트칠되지 않은 구역을 기준으로 최대한 오른쪽으로 길게 칠하면서 필요한 페인트칠 횟수를 최소화함
• 롤러 위치 지정: section에서 아직 페인트칠하지 않은 첫 번째 구역에 롤러를 놓고, m 길이만큼 칠한다. 칠할 때마다 그 다음 칠해야 할 구역으로 이동하며 페인트칠을 반복함

 

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int current = 0;

    for (int i = 0; i < section.size(); i++) {
        if (current < section[i]) {
            answer++;
            current = section[i] + m - 1;
        }
    }
    return answer;
}