[BOJ20164] 홀수 홀릭 호석 (완전탐색)

 

 

---

문제 링크 

https://www.acmicpc.net/problem/20164

20164번: 홀수 홀릭 호석

 

문제 풀이 

하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다.

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

 

- '수가 세자리 이상일 때 임의 위치에서 끊어서 3분할을 한다'는 것을 시야가 좁아져서 이해를 못해서 시간 소비함 

(문제 좀 잘 읽고, 긴장해서 시야 좁혀지는거 고칠 수 있도록 하자 !)

- 2중 for문으로 세자리수 이상인 경우 3분할을 할 수 있도록 처리함

- 1 ≤ N ≤ 10^9 - 1 에서 N은 최대 999,999,999 이고, 자리 수 별로 끊어서 처리하기 때문에 충분히 1초안에 연산이 가능하다

 

예시 입력2) 82019 를 3분할할 경우

8,2,019
8,20,19
8,201,9
82,0,19
82,01,9
820,1,9

 

 

제출 코드 

- countOdd() : 현재 숫자에서 홀수 개수 카운팅

- sum() : Spread operator 사용해서 String형 배열을 받아서 형변환 후 합산 결과 반환

- *.substring(int from, int to) 에서 to는 exclusive(제외) 이다

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N;
    
    static int MIN_VALUE, MAX_VALUE;
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        MIN_VALUE = Integer.MAX_VALUE;
        MAX_VALUE = Integer.MIN_VALUE;
    }

    static int countOdd(int num) {
        int result = 0;
        int value = num;
        while(value > 0) {
            int mod = value % 10;
            if(mod % 2 == 1) result += 1;

            value /= 10;
        }

        return result;
    }

    static int sum(String... numbers) {
        int result = 0;
        for(String n : numbers) {
            result += Integer.parseInt(n);
        }

        return result;
    }

    static void rec(int data, int oddCount) {
        // 숫자가 1자리 인 경우
        if(data <= 9) {
            oddCount += (data % 2 == 1 ? 1 : 0);
            MIN_VALUE = Math.min(MIN_VALUE, oddCount);
            MAX_VALUE = Math.max(MAX_VALUE, oddCount);
            return;
        }

        // 숫자가 2자리 인 경우
        if(data <= 99) {
            int v10 = data / 10;
            int v1 = data % 10;
            oddCount += (v10 % 2 == 1 ? 1 : 0);
            oddCount += (v1 % 2 == 1 ? 1 : 0);

            rec(v10 + v1, oddCount);
            return;
        }

        // 숫자가 3자리 이상인 경우, 임의 위치에서 끊어서 3개의 수로 분할
        if(data >= 100) {
            oddCount += countOdd(data);
            String num = String.valueOf(data);
            for(int i = 0; i < num.length() - 2; i++) {
                for(int j = i + 1; j < num.length() - 1; j++) {
                    String v1 = num.substring(0, i + 1);     // 0 ~ i
                    String v2 = num.substring(i + 1, j + 1); // i ~ j
                    String v3 = num.substring(j + 1);        // j ~ 끝까지 

                    rec(sum(v1, v2, v3), oddCount);
                }
            }
        }
    }

    static void pro() {
        rec(N, 0);

        sb.append(MIN_VALUE).append(" ").append(MAX_VALUE);

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
    
}