행복 유치원(백준 13164번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?✓

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상✓

3. 중

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

나의 풀이(오답)

N,K=map(int,input().split())
students=list(map(int,input().split()))

sub_st=[]
for i in range(1,len(students)):
    sub_st.append((students[i]-students[i-1],i))
sub_st.sort()

split_idx=[]
for _ in range(K-1):
    split_idx.append(sub_st.pop()[1])
split_idx.sort()
answer=0
pre_idx=0
for j in range(len(split_idx)):
    answer+=(students[split_idx[j]]-students[pre_idx])
    pre_idx=split_idx[j]+1
    if j==len(split_idx)-1:
        answer+=(students[-1]-students[pre_idx])
print(answer)

• 우선 유치원생들 사이의 모든 차이를 구해서, 그 차이가 가장 큰 부분을 기준으로 그룹을 만들어야 된다는 생각은 스스로 할 수 있었다. 하지만, 그 차이가 가장 큰 부분을 벽으로 생각하여 그 벽을 기준으로 나누어진 그룹의 가장 첫번째 원생과 가장 마지막 원생의 키 차이를 구하여 더하려는 생각부터 오류가 발생했던 것 같다. 오류가 해결되지 않아 솔루션을 참고했다.

나의 풀이(정답 참고)

N,K=map(int,input().split())
students=list(map(int,input().split()))

sub_st=[]
for i in range(1,len(students)):
    sub_st.append(students[i]-students[i-1])
sub_st.sort()

split_idx=[]
for _ in range(K-1):
    sub_st.pop()
print(sum(sub_st))

• 생각해보니, 이웃한 원생끼리의 모든 차이를 더하면 결국 가장 처음 원생과 가장 마지막 원생의 키 차이다. (ex. [1,3,4,6,7]⇒ 차이=7-1=(3-1)+(4-3)+(6-4)+(7-6)=6
• 따라서 그냥 단순하게, 모든 차이값에서 이웃한 원생의 키 차이 중 가장 큰 K개의 값만 빼주면 해결되는 것이다.
• 문제를 접근하는 방식까지는 아주 좋았는데, 결정적인 부분에서 판단을 못했다.