프로그래머스 lv2 덧칠하기

문제링크

덧칠하기

풀이

• 이미 칠해진 곳은 덧칠해도 상관없음

• 다만 최소로 칠하는 덧칠 횟수 찾기

• 탐색의 시작은 덧칠해야하는 곳에서 시작한다.

• 시작점 + 롤러너비를 max 값으로 잡아서 그 다음에 덧칠해야하는 빈벽의 인덱스가 max 값보다 작으면 그때는 pass 할 수 있도록 한다.

• 슈도코드로 짜보면 다음과 같다.
  

• 자바 코드로 짜면 다음과 같다.

  class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int max = 0;
  
        for (int i = 0; i < section.length; i++) {
            if (section[i] < max) {
                continue;
            }
  
            answer += 1;
            max = section[i] + m;
        }
  
        return answer;
    }
  }