프로그래머스 LV1 덧칠하기

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/161989

프로그래머스

풀이

이 문제를 이해하기 위해서 간단하게 문제에서 주어진 입출력 예제를 확인해 보자. 

칠해지지 않는 부분 (section) 은 항상 오름차순으로 주어진다. section 부분을 처음부터 순회하면서 덧칠해 나가고, 중복 덧칠을 최소한으로 줄인 상태로, 그 덧칠 횟수 계산하면 그 값이 최소 횟수가 된다.

 

현재 페인트가 칠해지지 않는 부분이 (2, 3, 6)의 부분이고 최대길이 n = 8, 칠하는 길이 m = 4의 조건으로 주어져 있다. 

 

 

현재 section이 다음과 같이 주어져 있는데, section에서 칠해지지 않은 부분이 (2, 3, 6) 이니까 2부터 시작해서 m - 1 만큼 페인트를 덧칠한다. 이때 페인트는  2 + m - 1 (5)까지 색칠이 된다. 

 

 

그다음 section 요소인 3을 덧칠하려고 하나, 이미 덧칠이 되어 있기 때문에 다음 요소로 넘어간다.

다음 요소는 6이므로 6을 기점으로 m - 1 만큼 페인트를 덧칠한다. 

더 이상 section에서 칠해지지 않는 부분이 없으니 이때까지 덧칠한 횟수 count는 2가 된다. 해당 부분을 코드로 작성하면 다음과 같다. 

def solution(n, m, section):
    
    # 덧칠 횟수
    count = 0 
    # 현재 덧칠된 구역
    cur = 0
    
    for element in section:
        if element > cur:
            count += 1
            cur = element + m + - 1
    
    return count