[BOJ] 20164. 홀수 홀릭 호석 (🥇, 브루트포스)

🔗

풀이

1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
2. 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
3. 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
4. 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

위의 과정을 반복한다. 새로운 수를 구하면 다시 1번부터 시작해서 과정을 반복한다. 수가 한 자리가 되어 아무것도 하지 못하고 종료될 때까지 해당 과정의 홀수의 개수를 모두 더하면 각 과정에 대한 홀수의 개수를 구할 수 있다. 그렇게 구한 각 과정의 홀수의 개수 가운데 최대와 최소값을 찾는 문제이다.

우선 coundOdd 를 통해 홀수의 개수를 구했다. 수가 한 자리면 더 이상 아무것도 하지 못하고 종료해야 하므로 종료하기 전에 최대, 최소값을 업데이트하고 종료했다. 2자리면 각 두 자리를 더해서 새로운 수를 만든 후 재귀로 calc 함수를 반복했다.

3자리의 경우 임의의 2개의 위치를 선정해서 3개의 수로 나눠야 한다.

임의의 2개의 위치 선정은 2중 for문을 통해 구했다. 위의 그림처럼 임의의 두 개의 위치를 선정하고 앞의 위치를 i, 뒤의 위치를 j 라고 했을 때 0~i까지의 합, i+1~j까지의 합, j+1~N까지의 합 세 개를 구한 후 더해서 새로운 수를 구하고 다시 재귀로 해당 과정을 반복 수행했다.

import java.io.*;
import java.util.*;

public class Main {
    static long maxCount;
    static long minCount = Long.MAX_VALUE;
    static String N;

    static void calc(String n, long oddCount) {
        oddCount += countOdd(n);
        if (n.length() == 1) {
            maxCount = Math.max(maxCount, oddCount);
            minCount = Math.min(minCount, oddCount);
            return;
        }

        if (n.length() == 2) {
            int tmp = Integer.parseInt(String.valueOf(n.charAt(0))) + Integer.parseInt(String.valueOf(n.charAt(1)));
            calc(String.valueOf(tmp), oddCount);
            return;
        }

        for (int i = 0; i < n.length() - 2; i++) {
            int front = getSum(n, 0, i);
            for (int j = i + 1; j < n.length()- 1; j++) {
                int middle = getSum(n, i + 1, j);
                int back = getSum(n, j + 1, n.length() - 1);
                int tmp = front + middle + back;
                String next = String.valueOf(tmp);
                calc(next, oddCount);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.next();

        /**
         * 1. 수에서 홀수의 개수 세기
         * 2. 수의 자릿수에 따른 연산
         * 2-1. 한 자리면 종료
         * 2-2. 두 자리면 2개로 나눠서 합하고 새로운 수 생성
         * 2-3. 세 자리 이상이면 "임의의 위치"에서 3개의 수로 분할(임의의 위치는 2군데) 3개를 더한 값을 새로운 수로 생각
         */
        calc(N, 0);
        System.out.println(minCount + " " + maxCount);
    }

    private static long countOdd(String n) {
        return Arrays.stream(n.split(""))
                     .mapToInt(Integer::parseInt)
                     .filter(i -> i % 2 == 1)
                     .count();
    }

    private static int getSum(String n, int startIdx, int endIdx) {
        return Integer.parseInt(n.substring(startIdx, endIdx+1));
    }
}