높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 평탄화라고 한다.
평탄화를 모두 수행하고 나면, 가장 높은 곳과 가장 낮은 곳의 차이가 최대 1 이내가 된다.
평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 제한된 횟수만큼 옮기는 작업을 한 후 최고점과 최저점의 차이를 반환하는 프로그램을 작성하시오.
단순한 Exhaustive Search가 아닌 다른 방법을 찾아보려고 했으나 실패.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import java.util.Scanner; public class Solution{ private static int testCase = 10; public static void main(String[] args){ Scanner sc = new Scanner(System.in); Solution sol = new Solution(); for(int inx = 0 ; inx < testCase ; inx++){ String input1 = sc.nextLine(); int dumpNum = Integer.parseInt(input1); String inputs = sc.nextLine(); String[] inputNumber = inputs != null ? inputs.split(" ") : null; int[] numbers = sol.convertIntVal(inputNumber); for(int c = 0 ; c < dumpNum ; c++){ int max = sol.getMaxIndex(numbers); int min = sol.getMinIndex(numbers); numbers[max] = numbers[max] - 1; numbers[min] = numbers[min] + 1; } int result = numbers[sol.getMaxIndex(numbers)] - numbers[ sol.getMinIndex(numbers)]; System.out.println("#"+String.valueOf(inx+1) + " " + String.valueOf(result)); } } public int[] convertIntVal(String[] numbers){ int[] result = new int[numbers.length]; for(int inx = 0 ; inx < numbers.length ; inx++){ result[inx] = Integer.parseInt(numbers[inx]); } return result; } public int getMaxIndex(int[] numbers){ int result = 0; int MaxNum = 0; for(int inx = 0 ; inx < numbers.length ; inx++){ if(MaxNum < numbers[inx]){ result = inx; MaxNum = numbers[inx]; } } return result; } public int getMinIndex(int[] numbers){ int result = 0; int MinNum = 100; for(int inx = 0 ; inx < numbers.length ; inx++){ if(MinNum > numbers[inx]){ result = inx; MinNum = numbers[inx]; } } return result; } } |