[프로그래머스] 덧칠하기

링크

문제 설명

def solution(n: int, m: int, section: list) -> int:
    ...

n은 벽의 길이, m은 롤러의길이, section은 칠해야할 구역의 번호가 담긴 리스트를 나타낸다. 롤러를 덧칠하기 위한 최소 횟수를 구하는 문제이다.

제한사항

• 1 ≤ m ≤ n ≤ 100,000
• 1 ≤ section의 길이 ≤ n
  • 1 ≤ section의 원소 ≤ n
  • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
  • section에서 같은 원소가 두 번 이상 나타나지 않습니다.
  • section의 원소는 오름차순으로 정렬되어 있습니다.

풀이

빈 벽을 만나면 롤러로 m만큼 색칠해나간다고 생각하면 된다. 즉 section을 순회하며 색칠을 시작한 벽의 번호 + m - 1보다 큰 번호를 만날 경우 색칠을 시작한 벽의 번호를 갱신한다. 위 그림의 예시를 들면 2번벽부터 색칠을 시작한다. 3번 벽의 경우 5보다 작기 때문에 이미 색칠이 됐고, 6번벽의 경우 5보다 크기 때문에 다시 색칠을 시작해야한다.

제출 코드

def solution(n: int, m: int, section: list) -> int:
    answer = 1
    curr = section[0]
    for s in section:
        if curr + m <= s:
            answer += 1
            curr = s

    return answer