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

프로그래머스

 

1. 문제

벽은 1 미터 길이의 구역 n 개로 나누고, 각 구역에 왼쪽부터 순서대로 1 번부터 n 번까지 번호가 붙어있습니다.

벽에 페인트를 칠하는 룰러의 길이는 m 미터이고, 룰러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

• 룰러가 벽에서 벗어나면 안 됩니다.
• 구역의 일부분만 포함되도록 칠하면 안 됩니다.

 

[입력]

정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section

 

[출력]

룰러로 페인트칠해야 하는 최소 횟수를 return

 

2. 제한사항

• 1 <= m <= n <= 100,000
• 1 <= section 의 길이 <= n

 

3. 풀이

벽의 가장 앞에서 부터 시작해 비어있는 모든 벽을 칠해야 하는 문제입니다.

때문에 만약 비어있는 벽을 만났을 때 반드시 칠해야 한다는 선택지 밖에 없습니다. 😭

 

이를 이용해, 벽이 있어 있을 때는 m 만큼 칠해주고, 이미 페인트가 칠해져 있는 칸일 경우에는 pass 하면 됩니다.

 

이를 코드로 표현하면 아래와 같습니다.

4. 코드

Python

def solution(n, m, section):
    answer = 0
    dp = [1] * n
    for s in section:
        dp[s-1]=0
    
    i = 0
    while i < n:
        if dp[i] == 0:
            answer+=1
            i+=m
        else: i+=1
    return answer