Bonuses

Code

public class Bonuses

{

    public int[] getDivision(int[] points) {

        int len = points.length;

        int sum = 0, extra = 100;

        boolean[] used = new boolean[len];

        int[] percents = new int[len];

        for (int i = 0; i < len; i++)

            sum += points[i];

        for (int i = 0; i < len; i++) {

            percents[i] = 100*points[i] / sum;

            extra -= 100*points[i] / sum;

        }

        while (extra-- > 0) {

            int max = 0, mi = 0;

            for (int i = 0; i < len; i++)

                if (!used[i] && points[i]>max) {max = points[i]; mi = i;}

            used[mi] = true;

            percents[mi]++;

        }

        return percents;

    }

}

Problem

고용자에게 상여금을 주기 위해, 모든 고용자의 점수에서 해당 고용자가 가진 점수의 퍼센트(소수점 절삭)를 구해 이 퍼센트로 상여금을 준다. 절삭된 소수점을 전부 더한 값이 1%가 넘으면, 제일 높은 퍼센트를 가진 고용자 순으로 1%씩 주어야 한다. 동일한 퍼센트일 경우 색인이 빠른 고용자부터 1%를 준다.

Explanation

처음에 double형을 이용해 문제를 풀었는데 해설을 참고해보니 double형을 쓰지 않고도 풀 수 있었다. 바로 (points[i] / sum) * 100 에서 (100 * points[i]) / sum으로 바꿔주면 된다. extra는 100으로 설정하고 소수점을 제외한 퍼센트 100 * points[i] / sum을 빼준다. 이러면 소수점 퍼센트를 쉽게 구할 수 있다.

References

https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm145