[그리디] 1931 회의실 배정, 13164 행복 유치원

1. 1931 회의실 배정

1.1. 문제유형

• 그리디

1.2. 해결과정

• 해당 문제는 (종료시간, 시작시간)을 기준으로 정렬한 후 카운트해야한다.

1. 회의를 가장 많이하려면, 빨리 끝나는 회의 먼저 시작한다.
2. 끝나는 시간이 동일하다면, 시작 시간이 빠른 회의를 먼저 시작한다.
3. 현재 종료된 회의시간 <= 다음 회의 시작시간, 이라면 다음 회의를 시작하고 카운트한다.

1.3. 소스코드

n = int(input())
rooms = [list(map(int,input().split())) for _ in range(n)]
rooms = sorted(rooms, key=lambda x: (x[1], x[0]))
answer = 0
end = 0

for s, e in rooms:
    if end <= s:
        answer+=1
        end = e

print(answer)

1.4. 노트필기

2. 13164 행복 유치원

2.1. 문제유형

• 그리디

2.2. 해결과정

• ⭐ 반드시 조를 나누지 않더라도 최소 '비용'은 구할 수 있다.
• ⭐ 최소 비용은 인접한 값들중에서 차이의 최소값을 우선적으로 묶는 것이다.
• 티셔츠 비용이 (조 안에서) 가장 큰 키 - 가장 작은 키이다.
• 조를 나누는 기준은 인접한 원생끼리 묶는다.
• 원생은 키 순으로 오름차순 정렬되어 있다.

2.3. 소스코드

n, k = map(int, input().split())
childs = list(map(int,input().split()))
diff = []
for i in range(1, n):
    diff.append(childs[i]-childs[i-1])

diff.sort()
result=0
for i in range(n-k):
    result+=diff[i]
print(result)

2.4. 노트필기