🧭 문제 분석
인호에게 M일 동안 N개의 약속이 있다.
각 약속의 기분 값은 H[i]로 표현되며, 약속이 있는 날로부터 하루가 지날 때마다 기분 값이 1씩 줄어든다.
이때 기분 값이 0 미만으로 떨어지면 우울 점수가 증가하게 된다.
우울 점수를 최소화 할 수 있는 약속 배치를 찾아라.
✅ 문제 풀이
우울 점수는 제곱으로 더해지기 때문에, 연속으로 유지될 수록 점수가 크게 높아진다.
예를 들어 약속이 없는 날이 3일 정도 있다고 하면,
연속으로 3일이 유지되었을 때 (1x1 + 2x2 + 3x3)로 14가 된다.
반면 이것을 떨어뜨려서 각각 1일씩 유지되게 한다면 (1x1 + 1x1 + 1x1)로 고작 3만 상승한다.
즉, 약속이 없는 날을 최대한 쪼개서 배치하면 우울 점수를 최소화 할 수 있다.
약속이 없는 날 계산
우선 약속은 기분 점수 + 1 만큼의 유지 효과를 갖는다. (0까지는 우울 점수가 증가하지 않으므로)
이를 고려했을 때 방학 M일 - (모든 약속의 기분 점수+1의 합)이 약속이 없는 날이라고 할 수 있다.
예제 입력 1을 예로 들면
2, 2, 1은 각각 3, 3, 2의 유지 효과를 갖고, 이것들의 합은 8이다.
M이 10이므로, 이 합 8을 빼면 약속이 없는 날은 2일이 된다.
약속이 없는 날 분산시키기
이제 약속을 최대한 분산시키는 것으로 우울 점수를 최소화 해보자.
예제 입력 1을 조금씩 바꿔가면서 예시를 들어보겠다.
3 8
2 2 1위와 같은 예시라면?
약속이 방학의 모든 날을 채워서 빈 자리가 없다. 즉, 우울 점수는 0이 된다.
3 9
2 2 1위와 같은 예시라면 방학이 빈 자리 하나가 생긴다.
이것은 어디에 배치하든 한 자리만을 차지한다. 즉, 우울 점수는 1이다.
3 10
2 2 1위와 같은 예시라면 빈 자리는 두개다.
이것은 약속 사이 사이에 배치하면 하나씩 갈라질 수 있다.
가능한 예시 (O가 빈자리)
OXXXOXXXXX
XXXOXXXOXX
XXOXXXOXXX
등등즉, 우울 점수는 (1 + 1) = 2 다.
3 11
2 2 1위 예시라면 빈 자리는 3개다.
이것 또한 약속 사이 사이에 배치하면 하나씩 갈라진다.
가능한 예시
OXXXOXXXOXX
XXXOXXXOXXO
등등즉, 우울 점수는 (1 + 1 + 1) = 3이다.
3 12
2 2 1위 예시는 빈 자리가 4개다.
약속의 앞뒤로 배치하면 이것도 하나씩 찢을 수 있다.
만약 빈 자리가 5개라면?
이때부터는 더이상 하나씩 찢을 수 없다. 약속의 앞뒤로 배치할 만큼 배치했기 때문이다.
이제는 연속 2개로 배치되는 빈자리가 생긴다.
즉, 2개, 1개, 1개, 1개로 배치된다.
빈 자리가 6개라면?
앞서 언급했듯이 제곱 수로 우울 점수가 더해지기 때문에 연속 3개의 빈자리는 지양해야 한다.
2개, 2개, 1개, 1개의 빈자리로 배치하는 게 맞다.
여기까지 왔으면 규칙이 눈에 보였을 것이다.
위 예시에서 남은 빈 자리가 5개가 됐을 때부터 빈 자리를 균일하게 찢을 수 없었다.
남는 빈 자리들을 추가적으로 하나씩 분산시켰다.
고로 빈 자리들을 약속의 앞 뒤 위치인 (N + 1)만큼 나눈 뒤, 나머지를 해당 위치들에 한개씩 분산시키면 된다.
만약 빈 자리가 N개 이하라면 무조건 약속 사이에 골고루 한개씩 배치할 수 있으므로 별 신경 쓸 필요 없다.
코드 작성
우선 입력을 받는다.
fun main() = with(System.`in`.bufferedReader()) {
val (N, M) = readLine().split(" ").map(String::toInt)
val H = mutableListOf<Int>().apply {
// N == 0인 경우도 있고, 그때는 입력이 없음
if (N > 0) addAll(readLine().split(" ").map(String::toInt))
}
...
}약속의 기분이 유지되는 일자를 모두 더하고, 그것을 M에서 뺌으로써 빈 자리를 구한다.
...
val sumVal = H.sumOf { it + 1 }
val left = (M - sumVal).coerceAtLeast(0)
...이제 앞서 말한 논리를 코드에 그대로 적용한다.
빈 자리가 N일 이하라면 모든 약속의 사이 사이에 배치할 수 있으므로, 우울 점수를 1만 추가하도록 찢을 수 있다. 그래서 빈 자리의 수를 그대로 출력하면 된다.
...
when {
left <= N -> print(left)
...
}
...빈 자리가 N일을 초과한다면 모든 약속 사이 사이에 균일하게 배치하고 나서, 나머지를 또 한번 균일하게 배치하는 것으로 우울 점수를 최소화 한다.
...
left > N -> {
val per = left.floorDiv(N + 1) // 약속 사이 사이에 균일하게 배치할 빈 자리
val mod = left % (N + 1) // 균일하게 배치해도 남은 빈 자리
val perSum = (1..per).sumOf { it * it } // 연속 적인 빈 자리가 만드는 우울 점수
// 남은 빈 자리는 각 자리에 하나씩 더 분산시킴.
// 그럼 우울한 날이 하루 더 연장되므로 (per + 1)일 만큼 우울하게 되고,
// perSum에 (per+1)^2을 더해주면 (per + 1)일 만큼 우울한 점수가 된다.
print((N + 1) * perSum + mod * (per + 1) * (per + 1))
}
}