문제 풀이
그리디
target = 프로젝트를 한 번만 실행해도 되도록 필요한 명예 점수
answer = 필요한 해커 수
프로젝트를 한 번만 실행해도 되려면 명예 점수가 1부터 1씩 차이나도록 존재해야 함
따라서 명예 점수를 오름차순으로 정렬하고 가장 작은 명예 점수부터 확인해서 target과 같도록 만들고 target을 증가시킴 이 때 target과 같도록 감소시켜야 하는 점수가 해커의 수이므로 answer에 더함
모든 명예 점수에 대해 반복하면 answer에 필요한 해커 수가 저장되어 있으므로 출력하면 정답
풀이 설명
명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 계속 할 수 있다. 하지만 명예 점수가 0 이하가 되는 순간 그들은 국회의원에서 박탈당하며 오랫동안 비난의 대상이 된다.
국회의원들에게 밀려 권력이 없는 왕은 프로젝트 “Defile”을 설계해 모든 국회의원을 없애버릴려고 한다. 프로젝트 “Defile”은 다음과 같은 방식으로 작동한다.
- 모든 국회의원을 모독해서 각각의 명예 점수를 1씩 감소시킨다.
- (1)로 인해 1명이라도 국회의원에서 박탈당한 사람이 발생했다면 국민들의 분노를 이용해 (1)로 돌아간다.
- (1)에 의해 국회의원에서 박탈당한 사람이 없다면 프로젝트를 종료한다.
프로젝트 자체가 명예롭지 못한 행동이기에 왕은 단 1번의 “Defile”을 실행해 모든 국회의원을 박탈시키고 싶다. 이를 위해 그는 전문해커집단 “제이나”에서 해커를 여러 명 고용했다. “제이나”에 소속된 각 해커는 사이버 상에 있는 흑역사를 추적해 국회의원 1명의 명예를 1만큼 감소시킬 수 있다. 이 역시 명예롭지 못하기에 왕은 최소한의 해커를 고용하려고 한다. 과연 왕은 최소 몇 명의 해커를 고용해야 할까?
즉, 한 번에 연쇄적으로 모든 국회의원이 박탈당해야 하므로 명예 점수가 1부터 1씩 증가하는 수열의 형태가 되어야 한다. 하지만 여기서 모든 명예 점수가 달라야 할 필요는 없기 때문에 같은 명예 점수는 있어도 상관이 없다.
따라서 명예 점수를 1씩 감소시켜 1부터 1씩 증가하는 수열의 형태로 만드려면 1부터 가장 차이가 적은 명예 점수를 감소시켜 만드는 것이다. 이를 하기 위해 명예 점수를 오름차순으로 정렬하고 현재 확인하는 명예 점수를 x, 수열의 형태로 만들기 위해 필요한 명예 점수를 target, 필요한 해커의 수를 answer로 정의한다.
명예 점수 x를 가장 작은 점수부터 오름차순의 순서로 확인하면서 이 점수가 target의 점수보다 크거나 같은지 확인한다. 같다면 필요한 명예 점수가 있는 것이므로 target만 증가시키면 되고, 크다면 target과 가장 차이가 적은 명예 점수가 x이므로 x를 target 만큼 감소시켜야 하기 때문에 이 차이를 answer에 더한다.
만약 x가 target보다 작다면 이미 확인한 명예 점수와 같다는 것이므로 따로 감소시킬 필요가 없기 때문에 다음 명예 점수를 확인하면 된다. 이를 모든 명예 점수에 대해 반복하면 필요한 해커의 수를 answer에 저장하고 있으므로 이를 출력하면 정답이 된다.
소스 코드
fun main(){
val br = System.`in`.bufferedReader()
val N = br.readLine().toInt()
val a = IntArray(N)
for(i in 0 until N){
a[i] = br.readLine().toInt()
}
a.sort()
var target = 1
var answer = 0L
for(x in a){
if(x >= target){
answer += x - target
target++
}
}
println(answer)
}