프로그래머스 - 덧칠하기

 

나의 풀이.

한 번에 칠할 수 있는 길이는 m이고 다시 칠하기로 한 구역은 적어도 한 번은 페인트칠을 해야하니까
section 배열 안의 요소들이 한번씩만 칠해지는 최소 횟수를 구하면 된다. 어렵다..

section 배열은 오름차순으로 되어 있어 0번째 인덱스의 값이 첫 시작 위치가 되면 된다.
예제 1번을 예로 들면 2부터 한번에 칠할 수 있는 끝인 5가 되어야 하기때문에
end 인덱스를 section[0] + m(칠할 수 있는 길이) 하면 6에서  -1 해야 원하는 길이가 된다.

그럼 다음 section배열 요소에서 5를 넘지 않으면 다시 칠할 필요가 없기 때문에 다음 요소로 넘어간다.
section[1]의 값은 3으로 이미 칠해진 범위기 때문에 넘어간다.
다음 section[2]의 경우 6으로 칠해진적이 없기 때문에 칠하는 횟수를 +1 해주고 end를 다시 잡아준다.
answer가 1인 이유는 처음에 한 번 칠하고 뒤에 조건을 돌기 때문임

만약에 1번 예제에서 6 뒤에 9가 있어 2, 3, 6, 9 라고 가정해도 정답은 2가 된다.
6에서 + 4 - 1 한게 끝점이 되서 9도 이미 칠해졌기 때문에 2가 되는것
처음에는 그림때문에 헷갈려서 중복칠하면 안되나 했는데 그런건 아녔다.
무튼 어려운 문제다..

    

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 1;
        int end = section[0] + m - 1;

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