홀수 홀릭 호석

📍 문제 설명

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

20164번: 홀수 홀릭 호석

 

💡 접근

수가 세 자리 이상일 때 각 자릿수에 따라서 규칙을 찾아보니 substring으로 분할하면 임의의 모든 위치로 끊을 수 있었다.

끊은 위치를 기준으로 반복해야하므로 재귀함수를 사용했고 수가 한자릿수일 때 min과 max를 갱신시켜주고 cnt를 리셋시켜줬다.

 

 

 

👩‍💻 코드

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

public class Main {
    static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    private static void dfs(String s, int cnt) {
        for(char c : s.toCharArray()) {
            int n = c - '0';
            if(n % 2 == 1) {
                cnt++;
            }
        }
        //수가 한자리 일 때 홀수의 갯수 갱신
        if(s.length() == 1) {
            max = Math.max(max, cnt);
            min = Math.min(min, cnt);
            cnt = 0;
            return;
        }

        //수가 두자리 일 때 -> 2개로 나눠서 합을 구하고 새로운 수로 생각
        if(s.length() == 2) {
            int first = s.charAt(0) - '0';
            int second = s.charAt(1) - '0';
            s = String.valueOf(first + second);
            dfs(s, cnt);
        }

        //수가 세자리일 때
        //세자리이상일 때 모든 임의의 위치에서 끊어봐야함
        if(s.length() >= 3) {
            //4자리일 때
            //i = 1 j = 2 j = 3
            //i = 2 j = 3
            //맨 처음의 값, 나머지는 합에 대한 값을
            for(int i = 1; i < s.length()-1; i++) {
                for(int j = i+1; j < s.length(); j++) {
                    int first = Integer.parseInt(s.substring(0, i));
                    int second = Integer.parseInt(s.substring(i, j));
                    int third = Integer.parseInt(s.substring(j, s.length()));
                    String str = String.valueOf(first + second + third);
                    dfs(str, cnt);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main t = new Main();
        String s = br.readLine();

        dfs(s, 0);

        System.out.println(min + " " + max);
    }

}