난이도 : Gold5
Link : https://www.acmicpc.net/problem/13164
Tag : 그리디 알고리즘, 정렬
풀이일자 : 2024년 8월 24일
📌 문제 탐색하기
N : 유치원 인원수
K : 팀의 갯수
height_list : 유치원 각원생 키
이 문제에서는 팀별로 인원을 나눴을 때 티셔츠를 만드는 비용의 합을 최소로 만들고 싶어 한다.
티셔츠를 만드는 방식은 팀 내에서 가장 작은 키 원생과 가장 큰 키 원생의 차이값이 티셔츠의 값이다.
단 팀원들은 서로 이웃해 있어야 한다.
가능한 시간복잡도
모든 팀원을 만들 수 있는 조합으로 생각한다면
nCk로 생각 할 수 있다. 하지만 티셔츠 만드는 비용의 합을 최소로 하므로 더 적게 탐색하며 시간 복잡도를 줄일 수 있는 최적의 해를 찾는 그리디 알고리즘으로 문제를 접근해보자.
📌 문제 접근 방법
팀을 짜기 위해서는 앞사람과 뒷사람이 가장 큰 키 차이를 가지고 있으면 그 둘은 다른 팀이 되는 것이 유리하다. 왜냐하면 문제에서 팀원들은 서로 이웃해 있다고 했기 때문이다.
따라서 먼저 모든 원생들의 키 차이를 배열에 저장해 가장 큰 차이를 기준으로 팀을 나눈다면 비용을 최소화 시킬 수 있다.
예를 들어
5 3
1 3 5 6 10
이렇게 입력이 들어왔을 때 인접한 원생의 키 차이는 다음과 같을 것이다.
dis = [2,2,1,4]
여기서 k가 2 일때는 다음과 같다.
큰 차이가 나는 5를 선택했을때 팀은 [1,3,5,6] , [10] 이렇게 두팀이 나눠지는 것이다.
k가 3이라면
큰 차이가 나는 2를 선택했을때 팀은 [1,3][5,6] [10] 이 되는 것이다.
여기서 중요한 점은 티셔츠를 만들 때 최소 비용으로 만들어야 한다. k가 2일때를 살펴보면
최소비용은 가장 큰 값을 제외한 다른 값들의 합과 같다. 2+2+1 = 6-1 이기 때문이다.
따라서 최적의 해를 내는 계산식을 생각해보면 다음과 같다.
dis 배열에서 k-1까지를 제외한 나머지를 더한다면 티셔츠를 만드는 최소비용이 나올 것이다.
📌 코드 설계하기
- n,k 를 입력받는다.
- height_list에 원생들의 키를 입력받는다.
- 원생들의 키 차이를 저장할 dis 배열을 만든다.
- 정답 변수 answer를 만든다.
- n-1까지 for문을 통해 이웃한 원생들의 키차이를 dis 배열에 저장한다.
- dis 배열을 내림차순으로 정렬한다.
- dis 배열에서 k-1까지를 제외한 나머지를 합하여 answer에 저장한다.
- answer 를 출력한다.
📌 시도 회차 수정 사항
1회 틀렸습니다. (sort 오름차순)
오름차순으로 정렬을 하게 되면 각 조의 비용을 계산하는데 가장 큰키와 가장 작은 키의 차이를 계산하는 곳에서 오류가 발생한다.
import sys
n,k = map(int,sys.stdin.readline().split())
height_list = list(map(int,sys.stdin.readline().split()))
dis = [] #각 인접한 유치원 생들의 키 차이
answer = 0
for i in range(n-1):
dis.append(height_list[i+1] - height_list[i]) #인접한 키 차이를 추가
dis = sorted(dis) #작은 순별로 정렬
for i in range(k-1):
answer += dis[i]
print(answer)
📌 정답 코드
import sys
n,k = map(int,sys.stdin.readline().split())
height_list = list(map(int,sys.stdin.readline().split()))
dis = [] #각 인접한 유치원 생들의 키 차이
answer = 0
for i in range(n-1):
dis.append(height_list[i+1] - height_list[i]) #인접한 키 차이를 추가
dis = sorted(dis, reverse=True) #큰 순별로 정렬
answer = sum(dis[k-1:])
print(answer)
