프로그래머스 덧칠하기 JAVA 풀이 (그리디)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

길이가 n미터인 벽이 있고, 다시 페인트칠해야 하는 구역들이 section 배열로 주어진다.

롤러의 길이는 m미터이며, 한 번 칠할 때 연속된 m개의 구역을 칠할 수 있다.

 

다시 칠해야 하는 모든 구역을 적어도 한 번 이상 칠할 때, 롤러를 사용하는 최소 횟수를 구하는 문제

---

📌 접근 방법

section 배열은 오름차순으로 정렬되어 있으므로 왼쪽부터 차례대로 확인한다.

현재까지 칠해진 마지막 구역을 end에 저장한다.

 

순회 중인 구역 s가 end보다 작거나 같다면 이미 칠해진 범위 안에 있으므로 넘어간다.

반대로 s가 end보다 크다면 아직 칠해지지 않은 구역이므로, 그 구역부터 롤러를 한 번 사용한다.

 

이때 칠해진 마지막 위치는 s + m - 1이 된다.

---

📌 핵심 아이디어

if (s > end) {
    answer++;
    end = s + m - 1;
}

end는 현재까지 페인트칠이 완료된 마지막 구역을 의미한다.

예를 들어 m = 4이고 s = 2라면, 2번 구역부터 칠했을 때 2, 3, 4, 5번 구역까지 칠할 수 있다.

 

따라서 end는 2 + 4 - 1 = 5가 된다.

이후 section에서 3번 구역이 나오면 이미 5번까지 칠해져 있으므로 추가로 칠하지 않아도 된다.

---

📌 전체 코드

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

---

📄 정리

이 문제는 다시 칠해야 하는 모든 구역을 직접 하나씩 칠하는 것이 아니라,

한 번 칠했을 때 어디까지 커버되는지를 관리하는 문제이다.

 

section 배열이 오름차순으로 정렬되어 있기 때문에,

왼쪽부터 보면서 아직 칠해지지 않은 구역을 만날 때만 롤러를 사용하면 된다.

 

n은 벽의 전체 길이를 의미하지만, 최소 횟수를 계산하는 과정에서는 다시 칠해야 하는 구역만 확인하면 되므로 직접 사용하지 않아도 된다.