문제
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
그리디 유형의 문제이다.
1. 색칠하는 횟수를 최소화하려면, 색칠된 부분을 다시 색칠할 필요가 없다는 것이라고 생각했다. 즉 그냥 skip 해버리면 된다는 생각을 했다.
2. skip을 하려면 어떤 구역에서 m칸 만큼 색칠하고 그 다음 구역 번호(paintPoint)를 알아야할 필요가 있다고 생각했다. (sections[i] + m부터 덧칠해야하는 구역 번호가 있다면 덧칠한다.)
3. paintPoint보다 현재 덧칠해야하는 구역 번호가 더 작으면, 이미 색칠이 된 것이므로, continue를 통해서 계속 i를 증가시킨다.
4. 색칠할때, 색칠 횟수를 기록한다.
소스코드
class Solution {
public int solution(int n, int m, int[] section) {
//색칠될 수 있는 시작 구역 번호
int paintPoint = 0;
int answer = 0;
for (int i = 0; i < section.length; i++) {
//section[i]가 이전에 덧칠해 있을 경우
if (paintPoint > section[i]) {
continue;
}
//색칠될 수 있는 시작 구역 번호 갱신
paintPoint = section[i] + m;
//색칠 횟수
answer += 1;
}
return answer;
}
}'Problem Solving > Programmers' 카테고리의 다른 글
| [Programmers] 카드 뭉치 - Java (0) | 2025.06.20 |
|---|---|
| [Programmers] 가장 가까운 같은 글자 - Java (0) | 2025.06.19 |
| [Programmers] 완전범죄 - Java (0) | 2025.06.17 |
| [Programmers] 가장 많이 받은 선물 - Java (0) | 2025.06.16 |
| [Programmers] 유연근무제 - Java (0) | 2025.06.15 |