이번에 풀어본 문제는
백준 20164번 홀수 홀릭 호석 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int MIN = Integer.MAX_VALUE,MAX = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        cut(input,getOdd(input));
        System.out.printf("%d %d",MIN,MAX);
    }
    static void cut(int n, int total)
    {
        // 한자리
        if(n < 10)
        {
            MIN = Math.min(MIN,total);
            MAX = Math.max(MAX,total);
        }

        // 두자리
        else if(n < 100)
        {
            int sum = (n / 10) + (n % 10);
            cut(sum,total+getOdd(sum));
        }

        else
        {
            String str = Integer.toString(n);
            int len = str.length();
            for(int i = 0; i <= len-3; ++i)
            {
                for(int j = i+1; j <= len-2; ++j)
                {
                    String s1 = str.substring(0,i+1);
                    String s2 = str.substring(i+1,j+1);
                    String s3 = str.substring(j+1,len);

                    int sum = Integer.parseInt(s1) + Integer.parseInt(s2) + Integer.parseInt(s3);
                    cut(sum,total+getOdd(sum));
                }
            }
        }
    }
    static int getOdd(int n)
    {
        int cnt = 0;

        while(n > 0)
        {
            //자릿수
            int cur = n % 10;
            if((cur % 2) == 1) cnt++;
            n /= 10;
        }
        return cnt;
    }
}

📝 풀이

한자리, 두자리 또는 그 이상의 자릿수를 가진 숫자를 주어진 규칙에 맞게 잘라나가면서 마주치는 홀수 개수의 최대,최솟값을 구하는 문제입니다.
수가 변할 때 마다 홀수 갯수를 카운트 해주는 getOdd함수와, dfs탐색을 진행합니다.
한자리, 두자릿수의 경우는 주어진 그대로 수행해 주면 됩니다.
세자리 이상일 때는 현재 숫자의 자료형을 String타입으로 바꾸어, 문자열을 잘라줍니다. 3등분이므로 2개의 반복문이 필요하고, 0부터 i, i부터 j, j부터 문자열의 끝까지 인덱스를 증가시키면서 자르면 모든 경우의 수를 탐색할 수 있습니다. 이후 과정은 위와 동일합니다.

📜 후기

완전탐색으로 문자열을 자르는 과정까지는 생각할 수 있었는데, 뭔가 그림으로 이해하다보니 인덱스의 사이를 잘라내는 느낌이어서, 반복문을 짜는 데 조금 헷갈렸던 문제입니다.