그리디 - 큰 수 구하기

n, m, k 세 개의 값을 받아서

n 만큼의 숫자를 배열에 담고, m 번 만큼 숫자를 나열하는데 한 숫자당 연달아 k만큼 가능하다.

 

n = 5, m = 5, k = 2

n = { 1, 2, 3, 4, 5} 

 

가장 큰 수의 조합은 5 5 4 5 5 형태가 된다.

 

   @Test
    void 그리디_큰수구하기() {
        // 같은 숫자를 연달아 k번 반복가능, m만큼 나열했을때 가장 큰수
        int m = 8;
        int k =3;

        /**
         * 만약 값을 입력받는다면 List로 받아서 Collections 정렬을 하자.
         * 배열로 받아서 Arrays.sort는 reverseOrder가 까다로움.
         */

        List<Integer> list = Lists.newArrayList(2, 6, 4, 5, 4);
        list.sort(Collections.reverseOrder());
        System.out.println(list);


        /**
         * 1번 내 풀이
         * 큰 수를 정렬 후 (8/3)*3*첫번째 큰 수 + (8%2)*두번째 큰수 = 제일 큰 수 조합
         */
        System.out.println(list.get(1) * (m % k) + list.get(0) * (m / k)  * k);

        /**
         *  2번 풀이
         *  (m / (k + 1)) * (첫째 수 * k + 두번째 큰수) + (m % (k + 1) * 첫째 수)
         */
        int front = (list.get(0) * k) + list.get(1);
        int count = m / (k + 1);

        int back = (m % (k + 1)) * list.get(0);

        System.out.println(front * count + back);
    }

 

문제가 너무 간단한거라 깊게 생각하지 않았다.

다만 2번 풀이 정답을 보고 내가 생각한 정답보다 규칙을 잘 만들었다는 느낌을 받았다.

나는 그냥 감으로 풀었다고 가정하면, 2번 풀이는 K+1과 같이 규칙을 새로 만들어서 그걸 적용한 느낌?