🔧 백준 1449번: 수리공 항승 문제 해결 방법

파이프에서 물이 새는 위치와 테이프 길이가 주어졌을 때, 필요한 테이프의 최소 개수를 구하는 문제입니다. 이 문제는 그리디 알고리즘을 활용해 효율적으로 해결할 수 있습니다.

📋 문제 핵심 이해

• 항승이: 수도 파이프 수리공
• 물이 새는 곳: 정수 위치에만 존재
• 테이프 특성: 길이 L, 무한개 보유
• 수리 조건: 물이 새는 위치 좌우 0.5 간격 필요
• 목표: 필요한 테이프의 최소 개수 구하기

💡 그리디 접근법

1. 최적의 테이프 배치 전략

• 물이 새는 위치를 _오름차순으로 정렬_하였다
• 가장 왼쪽에 있는 구멍부터 테이프 부착을 시작하였다
• 하나의 테이프로 커버 가능한 모든 구멍을 처리하였다

2. 알고리즘 구현 방법

– 물이 새는 위치에 테이프 시작점을 배치(좌우 0.5 고려)
– 테이프 하나가 커버하는 범위: 현재위치 - 0.5 ~ 현재위치 - 0.5 + L
– 이 범위 내 모든 구멍은 하나의 테이프로 처리 가능

🧮 코드 구현 전략

1. 배열 활용 방식

import sys
input = sys.stdin.readline
n, l = map(int, input().split())
coord = [False] * 1001  # 0~1000까지의 좌표를 False로 초기화
for i in map(int, input().split()):
    coord[i] = True  # 물이 새는 곳의 좌표를 True로 설정
cnt = 0  # 테이프 개수
x = 0  # 현재 위치
while x <= 1000:
    if coord[x]:  # 물이 새는 곳이면
        cnt += 1  # 테이프 개수 증가
        x += l  # 테이프 길이만큼 이동
    else:
        x += 1  # 물이 새지 않는 곳이면 다음 좌표로 이동
print(cnt)  # 테이프 개수 출력

2. 정렬 기반 방식

– 물이 새는 위치를 담은 배열을 정렬하였다
– 첫 번째 위치에 테이프를 붙이고 범위 계산하였다
– 범위를 벗어나는 위치가 나올 때마다 새 테이프 사용하였다

🔍 테스트 케이스 분석

예제 1: N=4, L=2, 위치=12100101

– 1, 2 위치를 _테이프 1개_로 막을 수 있다
– 100, 101 위치를 _테이프 1개_로 막을 수 있다
– 총 필요한 테이프: 2개

예제 2: N=4, L=3, 위치=1234

– 1, 2, 3 위치를 _테이프 1개_로 막을 수 있다
– 4 위치를 _테이프 1개_로 막을 수 있다
– 총 필요한 테이프: 2개

예제 3: N=3, L=1, 위치=321

– 각 위치마다 별도의 테이프가 필요하다
– 총 필요한 테이프: 3개

📊 좌표 압축 기법

1. 좌표 압축이란?

– 수의 범위가 매우 클 때 사용하는 기법이다11
– 좌표 간 대소관계만 유지하며 범위를 축소하였다
– 인덱싱으로 좌표 사이 갭을 제거하였다7

2. 적용 시나리오

– 물이 새는 위치가 10억 단위일 경우 배열 생성 불가능
– 이런 경우 위치 자체만 저장하고 정렬하여 처리하였다
– 이를 통해 메모리 사용량을 크게 줄일 수 있다

좌표 압축 예시:
원본 좌표: [5, 10, 2, 7, 13, -3]
압축 후: [2, 4, 1, 3, 5, 0]

🔑 문제 해결의 핵심

– 그리디 알고리즘의 정당성: 항상 최적해를 보장하였다9
– 왼쪽부터 순차적으로 처리하는 전략이 최소 테이프 개수를 보장하였다
– 정렬을 통한 효율적인 처리가 중요하였다

📚 결론

수리공 항승 문제는 그리디 알고리즘의 전형적인 예시이다. 물이 새는 위치를 정렬하고, 왼쪽부터 차례로 테이프를 붙이는 전략이 최적해를 보장한다. 또한 좌표 압축 기법을 통해 좌표 범위가 클 경우에도 효율적으로 문제를 해결할 수 있다.

Citations:

1. https://www.acmicpc.net/problem/1449
2. https://www.acmicpc.net/problem/1449
3. https://velog.io/@jiyaho/%EB%B0%B1%EC%A4%80-1449-%EC%88%98%EB%A6%AC%EA%B3%B5-%ED%95%AD%EC%8A%B9-Node.js-Greedy
4. https://www.youtube.com/watch?v=aYWRY9ZVKI0
5. https://sorryday.tistory.com/60
6. https://velog.io/@christer10/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A2%8C%ED%91%9C-%EC%95%95%EC%B6%95
7. https://torbjorn.tistory.com/274
8. https://velog.io/@153plane/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm
9. https://cs.stackexchange.com/questions/59964/how-to-prove-greedy-algorithm-is-correct
10. https://100100e.tistory.com/76
11. https://wikidocs.net/214469
12. https://beginnerdeveloper-lit.tistory.com/117
13. https://whyeskang.com/362
14. https://velog.io/@a87380/1449%EB%B2%88-%EC%88%98%EB%A6%AC%EA%B3%B5-%ED%95%AD%EC%8A%B9-%ED%8C%8C%EC%9D%B4%EC%8D%AC
15. https://runa-nam.tistory.com/36
16. https://developerhan.tistory.com/16
17. https://mango-juice.com/12
18. https://happybplus.tistory.com/451
19. https://jaewoo2233.tistory.com/46
20. https://dev-mandos.tistory.com/205
21. https://blog.naver.com/jqkt15/221813619810
22. https://read-me.tistory.com/entry/JAVABOJS3-1449-%EC%88%98%EB%A6%AC%EA%B3%B5-%ED%95%AD%EC%8A%B9
23. https://velog.io/@destudent/%EB%B0%B1%EC%A4%80-1449%EB%B2%88-%EC%88%98%EB%A6%AC%EA%B3%B5-%ED%95%AD%EC%8A%B9%ED%8C%8C%EC%9D%B4%EC%8D%AC
24. https://blog.naver.com/tlstjd436/222594722343
25. https://jordano-jackson.tistory.com/17
26. https://mingyum119.tistory.com/61
27. https://didu-story.tistory.com/393
28. https://kyuntechblog.tistory.com/52
29. https://velog.io/@ggh-png/series/boj
30. https://mangu.tistory.com/90
31. https://st-lab.tistory.com/279
32. https://jkimst.org/upload/pdf/KIMST-2020-23-4-381.pdf
33. https://www.khoury.northeastern.edu/home/vip/teach/Algorithms/5_greedy/notes/greedy.pdf
34. https://velog.io/@kjyeon1101/%EC%BD%94%ED%85%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-class-3-%EC%A2%8C%ED%91%9C-%EC%95%95%EC%B6%95
35. https://velog.io/@su9king/Coordinatecompression
36. https://aia1235.tistory.com/68
37. https://www.cs.ucr.edu/~yihans/teaching/141/f20/141F20/discussion/worksheet4.pdf
38. https://maloveforme.tistory.com/71
39. https://sh-avid-learner.tistory.com/243
40. https://gazelle-and-cs.tistory.com/59
41. https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/handouts/120%20Guide%20to%20Greedy%20Algorithms.pdf