[까다로운 문제]백준 13164: 행복 유치원 - javascript(그리디)

문제 출처 

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

13164번: 행복 유치원

문제

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

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

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

예제 입력 1 복사

5 3
1 3 5 6 10

예제 출력 1 복사

3

힌트

• 1조: 1, 3
• 2조: 5, 6
• 3조: 10

문제 풀이 힌트 

- 학생의 키 차이를 diff 배열에 push 한다. 

- diff 배열을 오름차순 정렬한다. 

- N-K-1 만큼 diff 의 요소를 다 더한다. 

 

그림으로, 더 자세히 설명해보자면 (사실, 내가 아직 이해가 안가서 그래요) 

 

먼저, 키 순서대로 서있는 학생들의 각 키의 차이를 diff 배열에 넣는다. 

=> 그 이유는 뒤에 설명하겠음 (나중에 조 짠거 보면 결국 이 차이들을 이용한 경우들밖에 나오지 않는다는 것을 알 수 있다. )

 

현재 k= 3으로 3개조가 있다. 

먼저 첫번째 경우를 들어보자 

키가 1인 학생 , 키가 3인 학생은 혼자 조를 하고 5,6,10 이 같은 조인 경우 => COST= 5

(혼자인 애들은 COST에 안넣음)

 

이 5라는 비용은 밑에 배열 2개에서 어떻게 나오는가? 

student = [1,3,5,6,10]

diff = [2,2,1,4]

5와 6의 차이인 1 과 6과 10의 차이인 4를 더한 값이라는 것을 알 수 있다. 

(그래서 뭐냐고? 일단 따라와봐라)

 

 

자, 2번째 경우를 한번 봐보자 cost = 6이다/ 

이 6이라는 비용은 밑에 배열 2개에서 어떻게 나오는가?

student = [1,3,5,6,10]

diff = [2,2,1,4]

1와 3의 차이인 2 와 6과 10의 차이인 4를 더한 값이라는 것을 알 수 있다. 

(옆에 숫자와의 차이를 이용해서 구해야 한다는 걸 알 것 같은가? )

 

cost를 구하는 모든 경우는 옆 숫자와 차이를 넣은 배열로 구하면 된다.

못 믿을까봐 다른 나머지 경우를 가져왔다.  

 

student = [1,3,5,6,10]

diff = [2,2,1,4]

정리하자면) 

1번 경우는 [2,2,1,4] 중 idx2과 idx3를 더한 값 

2번 경우는 [2,2,1,4] 중 idx0 과 idx3를 더한 값 

3번 경우는 [2,2,1,4] 중 idx0과 idx1를 더한 값 

.....

자 그럼 이 diff 를 조합해서 가장 최소값이 나오려면? 

diff 를 오름차순 정렬 한다. 

[1,2,2,4]

근데 몇개까지 더해야 하는가? 

diff.length - (K-1)

=>  N-K 로 표현 가능하다. (어처피 diff의 길이는 N보다 1작을테니까 쌤쌤 )

 

근데 왜 diff.length-(K-1)일까? 

다른 블로그에서도 설명은 안나와있어서 고민을 좀 해봤다. 

근데 봐보세요 ! 

 

1) diff 는 4개가 있다.  학생과 학생이 연결된 상태인데, 그 연결된 상태가 4개라는 뜻이다. 

 

 

2) 그런데 조가 3개이면 보이는 것 같이 연결이 두개가 끊어진게 보인다. 

조 개수에서 하나 뺀게 '끊어진 연결 개수'를 의미한다. 

(그림만 봐도 연결이 2개가 끊어져보이잖아요,,, 흑,,,)

 

 

여기서 설명을 그만해야 할 것 같다,,, 아무래도,, 제 최선이였어요 ㅜㅜ 흑,,, 더 성장해서 올게요,, 

 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [N, K] = input[0].split(' ').map(Number); 
const student = input[1].split(' ').map(Number); 
function solution(N, K, student){
    let diff = []; 
    let answer = 0; 
    for(let i=0; i<N-1; i++){
        diff.push(student[i+1] - student[i]); 
    }
    diff.sort((a,b)=> a-b); 
    for(let i=0; i< N-K; i++){
       answer += diff[i]
    }
    return answer; 
}
const answer = solution(N,K,student); 
console.log(answer);