[그리디] 코딩테스트 문제 TIL (수리공 항승) - 백준 1449번

말하는 감자·2024년 12월 26일

TIL baekjoon greedy python sorting 그리디 백준 정렬 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

53/67

1. 오늘의 학습 키워드

정렬
그리디

2. 문제: 1449. 수리공 항승

단계: 🥈 실버 3단계
주제:
- 그리디 알고리즘
- 정렬
출처: https://www.acmicpc.net/problem/1449

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력 1 복사

4 2
1 2 100 101

예제 출력 1 복사

예제 입력 2 복사

4 3
1 2 3 4

예제 출력 2 복사

예제 입력 3 복사

3 1
3 2 1

예제 출력 3 복사

3. 문제 풀이

Step1. 문제 이해하기

각 물이 새는 곳의 위치는 정수로 주어지며, 테이프는 특정 범위를 덮습니다. 새는 곳을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야합니다.

테에프는 겹쳐서 사용할 수 있고, 자를 수는 없습니다.

테이프의 길이는 L이며, 물이 새는 위치의 좌우로 각각 0.5씩 추가로 덮어야 물이 새지 않습니다. 목표는 물이 새는 위치를 모두 덮기 위해 필요한 최소 테이프 개수를 계산하는 것입니다.

입출력을 살펴보겠습니다.

Input:
- 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어집니다.
- 둘째 줄에는 물이 새는 곳의 위치가 주어집니다.
Output:
- 첫째 줄에 항승이가 필요한 테이프의 개수를 출력합니다.

Step2. 문제 분석하기

정렬:
- 물이 새는 위치는 정렬되지 않은 상태로 주어질 수 있습니다.
- 문제를 간단하게 풀기 위해 위치를 오름차순으로 정렬합니다.
테이프 설치:
- 가장 왼쪽에서부터 시작하여, 하나의 테이프가 커버할 수 있는 범위를 최대한 덮습니다.
- 테이프가 덮는 범위는 시작 위치+L−1 까지입니다.
- 커버할 수 없는 위치를 만나면 새로운 테이프를 설치합니다.
그리디 선택:
- 현재 위치에서 가능한 최대 범위를 덮는 테이프를 설치하는 선택은 전체 최소 테이프 개수를 보장합니다.

Step3. 코드 설계

입력 데이터 정리:
- 입력받은 위치 리스트 positions를 오름차순 정렬합니다. 이는 물이 새는 곳을 왼쪽에서 오른쪽으로 순차적으로 처리하기 위함입니다.
테이프 설치 과정:
- end_pos: 현재 테이프가 덮을 수 있는 마지막 위치를 나타냅니다.
- cnt: 설치한 테이프의 개수를 카운트합니다.
- 각 위치 position을 순회하면서:
  - 현재 위치 position이 end_pos를 초과하면 새 테이프를 설치해야 합니다.
  - 테이프를 설치한 후, end_pos를 해당 테이프가 덮을 수 있는 최대 범위로 갱신합니다.
최종 결과:
- 필요한 테이프의 개수 cnt를 출력합니다.

Step4. 코드 구현

import sys
N, L = map(int, sys.stdin.readline().split())
positions = list(map(int, sys.stdin.readline().split()))
def sol(N, L, positions):
    positions.sort()
    end_pos = 0
    cnt = 0
    for position in positions:
        if position > end_pos:
            cnt += 1
            end_pos = position + L - 1
    return cnt
print(sol(N=N, L=L, positions=positions))

코드 설명:

입력 처리 및 정렬:
```
N, L = map(int, sys.stdin.readline().split())
positions = list(map(int, sys.stdin.readline().split()))
positions.sort()
```
- 물이 새는 위치 리스트를 정렬하여, 왼쪽부터 차례대로 테이프를 설치할 수 있도록 준비합니다.

테이프 설치 로직:

end_pos = 0  # 현재 테이프가 덮을 수 있는 마지막 위치
cnt = 0      # 테이프 개수
for position in positions:
    if position > end_pos:  # 현재 위치가 테이프 범위를 벗어난 경우
        cnt += 1            # 새로운 테이프 설치
        end_pos = position + L - 1  # 새 테이프의 덮을 수 있는 범위 갱신
return cnt