Greedy Algorithm : 1449 수리공 상승

Greedy Algorithm

---

그리디 알고리즘은 알고리즘의 한 종류이다. 

그리디 알고리즘에서 Greedy 는 탐욕을 뜻한다. 

이 알고리즘은 미래의 상황을 따지지 않는다. 그 상황에서 가장 좋은 선택을 한다.

 

위키백과에는 다음과 같이 정의되어 있다.

 

 

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage

 

 

 

하지만 여기서 알고리즘을 푸는 우리가 생각할 것은 현재 상태에서 무엇이 최선의 선택인가일 것이다. 

매번 좋은 선택을 하면 최고이겠지만 매번 멍청한 선택을 하면 나락이다. 

 

 

 

 

 

수리공 상승 문제 

---

문제를 보면서 이해를 해보자. 문제 링크는 다음과 같다.

 

https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

 

문제 이해

---

이 문제는

 

다음과 같이 생긴 파이프 라인이 있을 때 이 파이프 라인에 구멍이 뚫려 있는 것이다. 

이 파이프라인에 테이프를 붙여서 구멍을 막아야 하는데 최소한의 테이프로 막는 것이 목표이다. 

 

때문에 우리가 생각해봐야 하는 것은 어떤 선택이 현재 상태에서 최선인가 이다.

 

우리는 무조건적으로 첫번째 구멍을 막아야한다. 이건 어떻게 해도 사실이다.

때문에 이 점을 이용해서 풀어야한다. 

 

첫번째 구멍을 막을 때 최대한 효율적으로 왼쪽 끄트머리를 구멍을 막을 수 있는 위치에 붙이면 된다. 

그렇게 되면 오른쪽에는 테이프가 남게 될 것이다.

 

오른쪽에 남은 테이프가 길어서 다른 구멍도 막아주면 땡큐이고 안 막아도 상관 없다.

어차피 이 구멍을 막아야만 하는 구멍이었으니까.

 

그리고 첫 번째 구멍을 막은 다음에 다음으로 뚫린 구멍을 첫번째 구멍이라고 생각하고 막으면 된다. 

 

이것을 반복하면 문제는 풀린다. 코드로 보면 다음과 같다.

 

코드

---

# 입력 받기
n, tape = map(int, input().split())
l = list(map(int, input().split()))

# 테이핑 되었는지 확인하기
taping = [0 for i in range(n)] 
l.sort()
cnt = 0

# 시간 복잡도 n 
# 앞에서부터 붙이면 됨. 붙인 부분은 무시함.
for i in range(n):
    if not taping[i]:
        taping[i] = 1

        # 같이 붙일 수 있는 애들 붙이기
        for j in range(1, n-i):
            if l[i+j] - l[i] + 1 <= tape:
                taping[i+j] = 1
        
        # 테이프 한번 썼음.
        cnt += 1

# 출력
print(cnt)