프로그래머스 | 덧칠하기 [파이썬 python]

프로그래머스

 

처음 시도한 코드

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

주어진 section의 0번째 값과 마지막 -1번의 값을 이용하여 범위를 구하였다.

그 범위가 롤러의 길이 m보다 크면 m으로 나눴을 때 몫과 나머지를 더하면 section[0]부터 section[-1]까지 칠해야 하는 횟수가 된다.

m보다 작거나 같으 1번 칠하면 되므로 answer=1이다.

 

하지만 이 코드에는 아주 큰 문제가 있었다.

예를 들어, 칠해야 하는 칸이 [2, 3, 15, 16]이라면 길이가 4인 롤러로 2부터 16까지 칠하게 된다.

하지만 4부터 14는 칠할 필요가 없기 때문에 이 코드로 구한 답은 최소 횟수가 아니다.

그래서 단순 계산이 아닌 최소 횟수를 구할 수 있는 다른 방법을 생각해야 했다.

 

정답 코드

def solution(n, m, section):
    answer = 1 # 칠하는 횟수
    paint = section[0] # 덧칠 시작점
    for i in range(1, len(section)):
        if section[i] - paint >= m:
            answer += 1
            paint = section[i]
            
    return answer

처음 시도했던 코드에서는 전체 section 범위를 구했지만, 정답 코드에서는 덧칠을 해야하는 구간인 section 요소들 간의 범위를 구하였다.

덧칠 시작점 paint를 section[0]으로 정해놓고 for문을 통해 paint와 section[i] 간의 간격을 구하였다.

 

롤러의 길이 m=4이면, 1, 2, 3, 4를 1번의 칠로 덧칠할 수 있으므로 1번의 칠로 가능한 범위는 4-1=3이므로 m-1이다.

m-1까지 1번으로 가능하므로 m부터는 2번이 되는 것이다.

따라서 section[i]-paint가 m이상이면 answer+1을 해주어야 한다.

 

그럼 1번의 칠을 완료했으므로 다음 칠할 구간을 찾아야 한다.

다음 칠 구간을 찾기 위해 section[i]를 paint 시작점으로 바꾸고 다시 범위를 찾는 과정인 for문을 반복한다.