문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 수학
홍준이는 한 고등학교의 수학 선생님이다. 기말고사 시험은 총 n명이 응시했다. 더 높은 점수를 받은 학생의 등수가 더 높다.
모든 채점이 끝났지만, 선생님은 학생들에게 다음과 같은 정보를 알려주었다.
모든 학생의 점수의 합은 p점이고, 상위 k명의 점수 중 서로 다른 점수의 수는 d.
위의 정보를 가지고 모든 학생의 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n, p, k, d가 주어진다. (1 ≤ k ≤ n ≤ 1000, 0 ≤ p ≤ 1,000,000, 1 ≤ d ≤ k)
출력
입력으로 주어진 n, p, k, d를 이용해서 만들 수 있는 점수를 등수가 높은 학생부터 순서대로 출력한다. 만약, 주어진 값을 이용해서 가능한 점수를 만들 수 없다면, "Wrong information"을 출력한다.
풀이
모든 학생의 점수의 합은 p점이고, 상위 k명의 점수 중 서로 다른 점수의 수는 d.
위의 정보를 가지고 모든 학생의 점수를 구해야 한다.
나는 d가 1일 때와 1이 아닐 때로 나눠서 풀었다.
d가 1이 아닐 때
상위 k명 중 d명만 다르면 되고, 초기 세팅 시 그 d명은 0부터 +1씩 점수를 가져야 가능성을 최대로 할 수 있다.
왜냐하면 그 d명의 점수 합이 p보다 작거나 같아야 되는데 d명의 점수 합이 작을 수록 조건에 만족할 확률이 높아지기 때문이다.
예를 들어
입력이 4 5 3 3이라고 했을 때,
모든 학생은 4명이고, 점수의 합은 5점이며, 상위 3명의 점수 중 서로 다른 점수의 수는 3이다.
상위 3명의 점수만 다르게 하면 된다. 그래서 가능성이 가장 높게 세팅하면,
2 1 0 0이 된다. 이때 상위 3명의 합이 p보다 크지 않다면 모든 학생의 점수를 구할 수 있다.
나머지 점수는 가장 점수가 높은 학생에게 더하면 되기 때문이다.
그래서 4 1 0 0이 정답이 된다.
앞에서 봤듯이 p보다 크지 않게끔 하려면 d명의 점수 합을 최소로 하는게 포인트다.
만약 3 2 1 0이로 초기 세팅을 했다면, 5(p)보다 3 + 2 + 1 합이 더 크기 때문에 "Wrong information"을 출력했을 것이다.
그래서 초기 세팅을 최적으로 하기 위한 방법을 일반화 하면 d-1 ~ 0 점수를 맨 앞에서부터 차례대로 부여해 주면된다.
d가 1일 때
d가 1일 때는 상위 k명의 점수가 다 같아야 한다. 그래서 d가 1이 아닐 때와는 다르게 풀어야 한다.
먼저, 상위 k명에게 p/k를 부여한다. 그리고 나머지 값으로 나머지 사람에게 p/k를 넘지 않은 값으로 분배해 준다.
상위 k명에게 p/k를 부여해 주는 이유는 동일한 값을 가질 수 있는 최댓값이기 때문이다. 그래야 나머지 값이 작아지고, 그 값을 나머지 사람에게 분배할 수 있는 확률이 최선이 되기 때문이다.
나머지 사람은 당연히 p/k를 넘어서면 안된다. 그러면 랭크가 변동되면서 조건을 위배하기 때문이다.
예를 들어
입력이 4 5 2 1일 때
모든 학생은 4명이고, 점수의 합은 5점이며, 상위 2명의 점수 중 서로 다른 점수의 수는 1이다.
상위 2명의 점수가 같기 때문에 동일한 값 중 최댓값을 부여한다. 그러면 상위 두 명은 2를 가진다. (5/2)
2 2 0 0이고, 남은 점수는 5%2 = 1이고, 나머지 사람은 2, 3 인덱스다.
이때 나머지 점수는 2보다 작기 때문에 2번 째 인덱스에 전부 할당해 줘도 문제 없다.
그래서 답은 2 2 1 0이 된다.
만약 나머지 사람 각각에게 2보다 같거나 작은 값을 전부 부여해 줬는데 남은 점수를 다 채우지 못했다면 이 경우는 "Wrong information"이다.
문제에 예제 입력 3을 해보면 쉽게 이해될 것이다.
시간 복잡도는 O(n)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int n, p, k, d;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
p = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
int[] students = new int[n];
boolean isPosible = false;
if(d != 1) {
int sum = 0;
for(int i = d - 1; i >= 0; i--) {
students[d - 1 - i] = i;
sum += students[d - 1 - i];
}
if(p >= sum) {
students[0] += p - sum;
isPosible = true;
}
} else {
//d가 1인 경우
//p / k만큼 상위 k명이 점수를 갖는다.
for(int i=0; i<k; i++) {
students[i] = p/k;
}
int min = p/k; //나머지 하위 랭크들은 p/k를 넘어서는 안됨
int mod = p%k;
for(int i=k; i<n; i++) {
if(mod - min > 0) {
mod -= min;
students[i] = min;
} else {
students[i] = mod;
mod = 0;
break;
}
}
if(mod == 0) {
isPosible = true;
}
}
if(isPosible) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
sb.append(students[i]).append("\n");
}
System.out.println(sb.toString().trim());
} else {
System.out.println("Wrong information");
}
}
}