프로그래머스 덧칠하기 문제 바로가기

문제에 대한 첫인상

처음 이 문제를 접했을 때 많이 당황했다. 최적의 경우를 어떻게 구하라는 건지… 특히 n과 m에 따른 관계를 파악하는게 어려워서 횟수를 기준으로 bruteforce해봐야하는지도 고민해보았다. 그런데 여러 예시들을 스스로 만들어보면서 n 변수는 솔직히 필요 없는 정보라는 점을 알게 되었다. 문제를 쉽게 바꾸면 section을 m길이 천막으로 모두 가리기 위한 천막의 갯수 정도로 생각해볼 수 있다.

따라서 section의 각 요소에 대해서 m 길이로 페인트를 칠하고, 칠해진 마지막 index을 업데이트 해나가는 논리를 따르면 greedy 방식으로 문제를 해결할 수 있다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int ans = 0;
    int tail = 0;
    // greedy
    for (int i: section){
        if (i > tail){
            ans += 1;
            tail = i + m - 1;
        }
    }
    return ans;
}