덧칠하기

오래 전에 풀이하다가 포기하고 다시 시도했는데, 그때는 문제 요구조건 그대로 완전탐색으로 시도했다. 요구조건을 조금 무시하더라도(예 : 최대 범위를 일부 넘기더라도) 풀이 알고리즘의 방향을 알면 빠르게 접근할 수 있다.

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int i, j;
        int current = 0, count = 0;
        
        //n : 벽 길이 1 ~ 100000
        //m : 롤러 길이 1 ~ 100000
        //section : 칠하기로 정한 구역들 번호 / 오름차순 정렬, 중복 없음
        
        //그리디 알고리즘? || DP?
        //1. 그리디 알고리즘으로
        for(i = 0; i < section.length; i++){
            if(section[i] > current){
                //System.out.print("현재 위치 : " + current + " -> ");
                count++;
                current = section[i] + m - 1;
                //System.out.println("현재 위치 : " + current);
            }
        }
        answer = count;
        
        return answer;
    }
}