(JAVA) Quantize 문제 오답이 나오는데 원인을 모르겠습니다.

  • hth0893
    hth0893
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.StringTokenizer;
    
    public class Main {
    
        public static void main(String[] args) throws NumberFormatException, IOException {
            // TODO Auto-generated method stub
            BufferedReader rb = new BufferedReader(new InputStreamReader(System.in));
            int testNum = Integer.parseInt(rb.readLine());
    
            for (int t = 0; t < testNum; t++) {
                StringTokenizer token = new StringTokenizer(rb.readLine());
                int arr[] = new int[Integer.parseInt(token.nextToken())];
                int quantNum = Integer.parseInt(token.nextToken());
    
                token = new StringTokenizer(rb.readLine());
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = Integer.parseInt(token.nextToken());
    
                }
    
                Quantization quantization = new Quantization(arr);
                System.out.println(quantization.quantize(0, quantNum));
            }
        }
    }
    
    //양자화를 할 때 
    class Quantization {
        int[] arr;
        // x 위치에서 y길이만큼 값을 설정 했을 때 결과 값
        int[][] cache = new int[101][11];
    
        public Quantization(int[] arr) {
            this.arr = arr;
            for (int i = 0; i < cache.length; i++) {
                Arrays.fill(cache[i], -1);
            }
            Arrays.sort(this.arr);
        }
    
        // 분할 개수
        int quantize(int start, int quant) {
    
            if (cache[start][quant] != -1) {
                return cache[start][quant];
            }
            // 양자수보다 남은 길이가 더 적을 때 모든 양자화 완료
            if (arr.length - start <= quant) {
                return 0;
            }
            // 양자화 수가 한개 남았을 때 계산
            if (quant == 1) {
                return getMinError(start, arr.length - start);
            }
            //일정량 양자화 후 남은 길이,양자화가능수 재귀호출
            int ret = Integer.MAX_VALUE;
            for (int i = start + 1; i <= arr.length - quant; i++) {
                int len = i - start;
                ret = Math.min(ret, getMinError(start, len) + quantize(i, quant - 1));
            }
    
            cache[start][quant] = ret;
            return ret;
        }
    
        // 양자화 결과값 리턴
        // start : 시작위치
        // size : 범위
        int getMinError(int start, int size) {
            int aver = 0;
            for (int i = start; i < start + size; i++) {
                aver += arr[i];
            }
            aver /= size;
            int averRet = 0;
            for (int i = start; i < start + size; i++) {
                averRet += Math.pow(Math.abs(arr[i] - aver), 2);
            }
            int aver1Ret = 0;
            for (int i = start; i < start + size; i++) {
                aver1Ret += Math.pow(Math.abs(arr[i] - (aver + 1)), 2);
            }
            return (averRet > aver1Ret) ? aver1Ret : averRet;
        }
    }// end Quantization
    

    여러개 예제입력을 추가해서 돌려봤는데 오류사항을 못찾겠어요

    추가적인 예제입력이 어떤게 더 있을지 아니면 어느 부분이 잘못된건지 알고싶습니다

    돌려본 예제 입력입니다.
    7
    10 3
    3 3 3 1 2 3 2 2 2 1
    9 3
    1 744 755 4 897 902 890 6 777
    2 3
    9 8
    1 2
    9
    3 2
    7 8 9
    4 1
    7 8 9 10
    4 2
    1000 1000 500 400

    예제입력 결과입니다.
    0
    651
    0
    0
    1
    6
    5000


    1달 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.