[코딩테스트] 덧칠하기

매일매일 코딩테스트

오늘의 잔디채우기는 LV.1의 덧칠하기

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

프로그래머스

문제 : 이미 칠해진 구간을 건너뛰고 answer를 증가시키는 타이밍을 어떻게 잡아야 할지 몰라 막혔다.

특히, i++처럼 한 칸씩 이동하면 중복 계산이 생기는데,
얼마나 건너뛰어야 하는지를 계산해서 불필요한 연산을 줄이는 구조가 떠오르지 않았다.

 

해결 : 

• paintedUntil: 지금까지 롤러로 칠해진 마지막 위치
• section[i] > paintedUntil: 아직 칠하지 못한 구간이면 롤러 사용

 

#include <string>
#include <vector>

using namespace std;

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

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