2024.05.23 TIL 코트카타 59번(덧칠하기)

class Solution {
    fun solution(n: Int, m: Int, section: IntArray): Int {
        var answer: Int = 1

        var startWall = section[0]

        for(wall in section) {

            if(startWall + m > wall)
                continue

            startWall = wall
            answer++
        }

        return answer
    }
}

 

- 오래 걸렸던 이유

   - 벽을 칠하는 경우의 수를 전부 조합으로 만들어서 완전탐색을 하려고 했다.(문제를 너무 복잡하게 생각했다.)

   - n이 100,000이기 때문에 조합으로는 시간초과나는 케이스가 많았다.(정답 또는 시간초과만 발생)

   - n이 크기 때문에 조합이 아닌 방법으로 접근해야 했다.

 

- 포인트

   1. section에 있는 벽을 첫 번째 칠하는 벽으로 선택한다.

   2. 해당 벽칠의 범위에서 필요한 다른 벽도 칠해졌는지 체크한다.

   3. 칠해지지 않은 가장 가까운 벽으로 이동해 1,2번을 반복한다.