[PGS] 덧칠하기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        
        int start = section[0];
        answer++;
        
        for (int s: section) {
            if (start + m > s) {
                continue;
            }
            start = s;
            answer++;
        }
        return answer;
    }
}

📄 해설

접근

• 그리디 알고리즘을 사용해서 풀이했다.
• 한번의 페인트칠로 최대한 많은 구역을 칠해야 하고, 칠해야 하는 구역의 번호는 오름차순으로 입력이 된다. -> 칠해야하는 구역을 페인트 칠의 시작점으로 해야한다. => 그리디 알고리즘을 사용한다.
• section 을 순회하며, 페인트 칠의 시작점 + 롤러의 크기 보다 작은 번호의 구역은 이미 색칠한 것으로 간주하고, 이 과정을 반복한다.

과정

• 페인트 칠의 시작점 변수 start 는 section[0] 로 초기화하고, section 을 순회하면서 start + m > s 인 경우는 이미 색칠이 된 경우로 간주한다.
• 그 외의 경우, answer 의 값을 증가시키고, start 를 s 로 초기화 한다.
• 위 두 과정을 반복하면 된다.