< 프로그래머스 C++ > 페인트 칠하기

문제 설명

길이 n미터인 벽을 길이 m미터짜리 롤러로 칠하는 문제이다.

다시 칠해야 할 구역 번호가 담긴 section이 주어질 때, 모든 구역을 칠하는 최소 횟수를 구하면 된다.

항목	예시 1	예시 2	예시 3
n	8	5	4
m	4	4	1
section	[2, 3, 6]	[1, 3]	[1, 2, 3, 4]
result	2	1	4

---

문제 해석

이 문제의 포인트는 지금 칠해야 할 구역이 이미 칠해진 범위 안에 있는지 확인하는 거다.

section을 앞에서부터 보면서

• 아직 안 칠해진 구역 > 거기서부터 롤러 한 번 칠하기
• 이미 칠해진 구역 > 그냥 건너뛰기

이렇게 그리디하게 처리하면 항상 최소 횟수가 나온다.
section이 오름차순으로 주어지기 때문에 앞에서부터 순서대로 처리해도 문제 없다.

---

문제 풀이

#include <string>
#include <vector>
using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int paint = 0;  // 마지막으로 칠해진 구역 번호

    for(int i = 0; i < section.size(); ++i)
    {
        if(section[i] > paint)          // 아직 안 칠해진 구역이면
        {
            paint = section[i] + m - 1; // 여기서부터 m칸 칠하기
            answer++;
        }
    }

    return answer;
}

---

핵심 포인트

1. paint 변수로 "어디까지 칠했는지" 추적

int paint = 0;

paint는 마지막으로 칠해진 구역 번호다.
section의 각 구역이 paint보다 크면 아직 안 칠해진 곳이라는 뜻이다.

2. 롤러 끝 위치 계산

paint = section[i] + m - 1;

section[i]에서 롤러를 시작하면 오른쪽 끝은 section[i] + m - 1이 된다
예를 들어, 2번 구역에서 길이 4짜리 롤러를 칠하면 2, 3, 4, 5번 구역이 칠해지고 paint = 5가 된다.

---

코드 흐름

예시의 n = 8, m = 4, section=[2, 3, 6]을 작성한 코드대로 흐름을 살펴보겠다.

항목	i = 0	i = 1	i = 2
section[i]	2	3	6
paint	0	5	5
section[i] > paint?	2 > 0  (true)	3 > 5 (false)	6 > 5 (true)
처리	2~5번 칠하기	건너뜀	6~9번 칠하기
paint 갱신	2+4-1 = 5	변화 없음	6+4-1 = 9
answer	1	1	2

 

결과는 2가 나와서 예시의 정답과 같은 것을 확인할 수 있다.