[LV.3] 연습문제 > 덧칠하기

문제

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

프로그래머스

---

문제 설명

• 상황
  • 길이 n의 벽이 있고, 1부터 n까지 번호가 붙은 1미터 단위의 구역으로 나뉘어 있음
  • 페인트가 벗겨진 구역 번호들이 section 배열로 주어짐
  • 롤러의 길이는 m미터이며, 한 번에 연속된 m개 구역을 칠할 수 있음
  • 롤러는 벽을 벗어나면 안 되며, 구역 일부만 칠할 수 없음
• 목표
  • section에 있는 모든 구역을 최소한의 롤러 횟수로 다시 칠하기
  • 한 구역은 여러 번 칠해도 되지만, section의 각 구역은 최소 한 번 이상 칠해야 함
• 제한사항
  • 1 ≤ m ≤ n ≤ 100,000
  • 1 ≤ section의 길이 ≤ n
  • section은 오름차순이며 중복 없음

---

---

정답 코드

def solution(n, m, section):
    count = 0
    last_painted = 0

    for pos in section:
        if pos > last_painted:
            count += 1
            last_painted = pos + m - 1

    return count

---

코드 설명

def solution(n, m, section):
    count = 0                  # 롤러를 사용한 횟수
    last_painted = 0           # 마지막으로 롤러가 칠한 구역의 끝 번호

    for pos in section:        # 다시 칠해야 하는 각 구역을 순서대로 확인
        if pos > last_painted:          # 아직 롤러로 칠하지 않은 구역이면
            count += 1                  # 롤러 1회 사용
            last_painted = pos + m - 1  # 현재 위치부터 롤러로 m칸 칠함 (끝 위치 갱신)

    return count               # 최소 롤러 사용 횟수 반환

---

첫 번째 시도 (실패)

def solution(n, m, section):
    
    if section[-1] > (section[0] + (m-1)):
        answer = (section[-1] - (section[0] + (m-1))) + 1
    else:
        answer = 1
                      
    return answer

---

틀린 이유

 

• if section[-1] > section[0] + (m - 1):
  • 시작과 끝 구역만 비교하여 최소 칠 횟수를 추정
  • 중간에 구간이 벌어진 경우(간격이 넓은 경우)는 고려하지 않기 때문에 정확한 최소 횟수를 계산할 수 없음
• 예시
  • 벽의 길이: n = 10, 롤러 길이: m = 3
  • 다시 칠해야 할 구역: section = [1, 2, 6, 7, 8]

벽 구역 번호:   1  2  3  4  5  6  7  8  9  10
페인트 필요:    ■  ■  □  □  □  ■  ■  ■  □  □

2번 칠하면 (123, 678) 충분하지만
기존 코드는 8 - 3 + 1 = 6번 칠해야 한다고 계산

---

두 번째 시도 (실패)

def solution(n, m, section):
    count = 0
    roll_end = 0
    
    for s in section:
        if s > roll_end:
            count += 1
            roll_end += (s + m - 1)
            
    return count

---

틀린 이유

• roll_end += (s + m - 1)
  • roll_end는 이번 롤러가 끝나는 위치를 저장해야 하므로 누적해서 더하면 안됨