[백준 09440] 숫자 더하기 [Java]

문제

http://boj.ma/9440

9440번: 숫자 더하기

 

---

풀이

문제 요약

N개의 수를 사용해 합이 최소인 두 수를 만들자.

아이디어

두 수의 합이 최소가 되기 위해서는, 주어진 수를 오름차순으로 정렬 후 번갈아 사용해 두 수를 만들면 된다.

두 수의 큰 자릿수에 작은 수를 부여해야 두 수의 합이 작아지기 때문이다.

N개의 수의 빈도를 구하고,

0이 아닌 가장 작은 수를 두 수에 부여한 후,

남은 수들을 번갈아가며 부여하면 된다.

public class Main {
    private static int solve(int[] A, int N) {
        ...  
        int[] nums = new int[2];
        for (int idx = 0; idx < 2; ++idx) {
            for (int i = 1; i <= 9; ++i) {
                if (count[i] > 0) {
                    --count[i];
                    nums[idx] = i;
                    break;
                }
            }
        }
        boolean isLeft = true;
        for (int i = 0; i <= 9; ++i) {
            while (count[i]-- > 0) {
                if (isLeft) {
                    nums[0] = nums[0] * 10 + i;
                } else {
                    nums[1] = nums[1] * 10 + i;
                }
                isLeft = !isLeft;
            }
        }
        return nums[0] + nums[1];
    }

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/09440.java

problem-solving/baekjoon-online-judge/easy/09440.java at main · rogi-rogi/problem-solving