[BOJ] 13164 - 행복 유치원

문제 출처

[BOJ] 13164 - 행복 유치원

 

풀이

유치원에서 N명의 원생들을 키 순서대로 줄 세우고 조를 나누어 티셔츠를 맞추려고 합니다. 조마다 티셔츠 맞추는 비용은 해당 조의 가장 큰 키의 원생 - 가장 작은 키의 원생 입니다. 

 

원생이 키 순서대로 서있고, 서있는 원생이 인접한 원생들로 조를 이루어야 합니다. 각 원생이 바로 뒤의 원생과 얼마나 키차이가 나는지 확인하여 그 중에서 큰 수들을 조를 이루어야하는 수보다 1 작은 수 만큼 빼주면 그 수를 기점으로 조를 나누게 됩니다. 

 

가장 차이나는 수가 큰 부분을 잘라서 조를 이루면 가장 작은 티셔츠 비용이 나오게 됩니다.

 

코드

small-j/Algorithm