프로그래머스, 덧칠하기(python)

문제 설명

벽의 길이 n과 롤러의 길이 m이 주어진다. 이때 벽은 중간 중간 비어 있는 부분이 있다. 이때 주어진 롤러를 이용해 벽을 얼마나 적은 수로 칠할 수 있는지 구하는 문제다. 이때 롤러는 벽 밖을 칠할 수 없고 중간에 끊을 수도 없다.

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

프로그래머스

문제 풀이

첫 번째 접근

처음에는 총 벽의 길이를 구해준 다음에 벽이 빌 때마다 칠해주도록 반복문을 작성했다. 그러나 롤러는 벽 밖을 칠할 수 없기에 롤러의 길이 만큼 빼서 범위를 지정해 주었는데, 여기서 문제가 생겼다. 그렇게 되면 남은 벽을 적절하게 칠할 수 없기 때문이다.

 

두 번째 접근

풀이를 찾아보니 빈 벽이 있는 section의 첫 번째 값을 시작으로 정해주고 다음 비어있는 벽마다 칸을 세어줘서 만일 그 칸의 수가 롤러의 길이보다 같거나 크면 칠해주는 방법이었다.

 

프로그래머스의 입출력 예 1을 보자.

벽이 총 8이고 롤러의 길이가 4인데, 벽이 비어 있는 부분은 '2, 3, 6'이다. 이때 벽 2부터 칠한다고 생각을 해보자. 그러면 일단 2를 칠했으니 answer를 1로 올려준다. 그리고 3과 2를 빼준다. 이때 값은 1으로 또 칠하기에는 너무 값이 작다. 그러므로 다음으로 옮겨서 6과 2를 빼준다. 이때의 값은 4. 롤러를 칠할 만큼 충분하므로 answer를 하나 올려주고 다음 부분으로 넘어간다. 그런데 6이 마지막 부분이니 반복문을 탈출하게 된다.

 

간단하게 말하자면 그 다음 칠해야 할 구역과 현재 칠할 구역 사이의 거리를 가늠한 다음에 충분히 그 거리가 커서 롤러로 칠할 수 있으면 칠해주는 방식이다.

 

코드

def solution(n, m, section):
    answer = 1 # section 시작 값에 먼저 칠해준다.
    start = section[0]
    
    for i in range(0, len(section)):
        if section[i] - start >= m:
            # 만일 끝칸과 시작 칸의 차이가 롤러의 길이보다 크거나 같다면
            answer += 1
            start = section[i]
    
    return answer