코드

n, l = map(int, input().split())
arr = list(map(int , input().split()))

arr.sort()

def solution(n, l, arr):

    # 붙일 테이프 개수 (최종 정답 변수)
    cnt = 1

    # 두 파이프 사이 간격
    dist = 0

    # 반복
    for i in range(1, n):
        
        # 사이 간격의 누적합을 구함
        dist += arr[i]-arr[i-1]

        # 같다(==) 조건이 없는 이유
        # 파이프 양쪽에 0.5의 간격이 필요하다고 했음
        # => l이 dist보다 커야만 확실하게 막을 수 있는 경우가 됨
        # 두 파이프 사이의 간격보다 테이프의 길이가 긴 경우만 해당 됨 (같으면 안 됨)
        
        # 테이프의 길이가 사이 간격의 누적합보다 크다?
        # 이전까지 테이프 개수로 만든 길이만으로 충분히 커버 가능
        # 반복 넘김
        if l > dist:
            continue
            
        # 누적합보다 같거나 작다?
        # 테이프를 하나 추가하고
        # 누적합을 0으로 초기화함 (거기서부터 또 최소 테이프 길이부터 연산 시작)
        else:
            cnt += 1
            dist = 0
            
    return cnt

print(solution(n, l, arr))

문제 해설

그리디 알고리즘 문제.

문제 자체가 요구하는 바를 명확하게 이해하는 것이 매우 어려운 문제였다.

테이프로 누수를 막으면 되는 조건인데, 한 곳의 누수를 막을 때 좌우로 0.5의 간격이 필요하다는 조건이 있다. 처음 이 조건이 의미하는 바를 도무지 파악하지 못해 애를 먹었다. 조건의 의미는 아래와 같다.

만약 누수된 두 파이프의 사이 간격이 3이라면, 필요한 테이프 길이는 3 + 0.5 + 0.5이다.

이를 간단하게 생각해보면, 테이프 길이가 누수 간격과 같은 경우도 누수 간격보다 작은 경우로 생각해도 된다는 의미이다. 따라서 이를 조건으로 적어보면

# 같다(==) 조건이 없는 이유
# 파이프 양쪽에 0.5의 간격이 필요하다고 했음
# => l이 dist보다 커야만 확실하게 막을 수 있는 경우가 됨
# 두 파이프 사이의 간격보다 테이프의 길이가 긴 경우만 해당 됨 (같으면 안 됨)

# 테이프의 길이가 사이 간격의 누적합보다 크다?
# 이전까지 테이프 개수로 만든 길이만으로 충분히 커버 가능
# 반복 넘김
if l > dist:
    continue

    # 누적합보다 같거나 작다?
    # 테이프를 하나 추가하고
    # 누적합을 0으로 초기화함 (거기서부터 또 최소 테이프 길이부터 연산 시작)
else:
    cnt += 1
    dist = 0

위처럼 코드로 나타낼 수 있다.

댓글남기기

참고