[Python] 2212번 센서 / 13164번 행복 유치원

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

2212번: 센서

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

13164번: 행복 유치원

---

 

22/10/06

 

 

두 문제는 문제 설명과 입력 형식만 다르고 풀이가 같은 문제이기 때문에, 한 문제로 엮어서 설명하겠다.

 

전형적인 그리디 문제로, 차이를 최소화하도록 구성하면 되는 문제이다.

---

 

문제 접근 방식:

 

 

행복 유치원 문제를 기준으로 설명하겠다.

 

티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 작은 원생의 키 차이만큼 소모된다.

 

이때, 우리는 티셔츠를 만드는 비용이 최소가 되도록 K개의 조로 나눌 때, 그때의 최소 비용을 알고 싶은 것이 우리의 목적이다.

 

먼저, 원생들을 키 순서대로 정렬하자.

 

그리고 나서 원생과 원생 사이의 키 차이의 리스트들을 만들어 준다.

 

예를 들자면, 원생의 키가 1, 6, 3, 10, 5로 주어져있다면, 이 원생들은 1, 3, 5, 6, 10과 같이 배열된다.

 

이후 양 옆끼리의 키 차이 리스트를 만들어주면, 2, 2, 1, 4와 같이 된다.

 

우리는 티셔츠를 만드는 비용이 최소가 되도록, 다시 말하자면, 키 차이가 최소가 되도록 K개의 조로 나누고 싶은 것이다.

 

예를 들어 원생을 3개의 조로 나눈다고 하면, 1과 3을 묶고, 5와 6을 묶고 10만 따로 묶으면 키 차이가 최소가 되도록 나눈 것이다.

 

왜냐하면, 1과 3사이의 차이는 2, 5와 6 사이의 차이는 1, 10과 10 사이의 차이는 0이기 때문이다.

 

결론을 말하면, K개의 조로 나누고 티셔츠의 비용을 전부 구하는 것은 저기 위의 키 차이 리스트 중에서 (K-1) 개의 숫자를 택하고 그 숫자를 더하는 것과 같다.

 

그리고 우리는 키 차이가 최소가 되도록 하고 싶은 것이 우리의 목적이므로, (K-1)개의 숫자를 택할 때, 가장 작은 것부터 차례대로 택하면 된다.

 

센서 문제도 마찬가지로 이와 똑같이 접근하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2212번 센서
# 정렬, 그리디
'''
접근 방법:
정렬 후 차이 구함
차이들 정렬 후 top K-1개 제거
이후 sum
'''
import sys
input = sys.stdin.readline

N = int(input())
K = int(input())
sensor = sorted(map(int, input().rstrip().split()))
diff = sorted(sensor[i+1] - sensor[i] for i in range(len(sensor)-1))
if diff == []:
    print(0)
else:
    for _ in range(K-1):
        diff.pop()
    print(sum(diff))

# 13164번 행복 유치원
# 정렬, 그리디
'''
접근 방법:
2212번과 같음
'''
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
tshirt = list(map(int, input().rstrip().split()))
diff = sorted(tshirt[i+1] - tshirt[i] for i in range(len(tshirt)-1))
if diff == []:
    print(0)
else:
    for _ in range(K-1):
        diff.pop()
    print(sum(diff))