20164번(홀수 홀릭 호석)

첫 시도

• N이 10^9-1라서 시간복잡도가 클 것 같지만 이 문제에서는 수의 값보다 수의 length와 관계있기 때문에 생각보다 시간복잡도가 얼마 안나온다.
• 어떤 숫자 내 홀수의 개수를 구하는 시간복잡도는 최악의 경우 9번, O(1)이다.
• 세 자리 수 이상일 때 그 수를 임의로 3개의 수로 분할하는 시간복잡도도 최악의 경우 6*7정도 나온다.
• min과 max를 만들고 재귀로 상황별 홀수의 갯수를 확인해 min, max를 갱신해준다.
• 풀이는 생각해냈는데 구현에서 1시간 초과

해결

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static intmax= 0;
    static intmin= Integer.MAX_VALUE;
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        dfs(N,countOdd(N));
        System.out.println(min+" "+max);
    }
    static void dfs(int num, int count){
        if(num < 10) {
            min= Math.min(min,count);
            max= Math.max(max,count);
        }
        else if(num < 100) {
            int sum = (num / 10) + (num % 10);
            dfs(sum,count+countOdd(sum));
        }

        else {
            String str = Integer.toString(num);
            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);
                    dfs(sum,count+countOdd(sum));
                }
            }
        }
    }
    static int countOdd(int num){
        int result = 0;
        while(num>0){ // 최대 9번
            int temp = num % 10;
            if(temp%2 == 1) result++;
            num /= 10;
        }
        return result;
    }

}

참고

• https://velog.io/@jh5253/백준-20164-홀수-홀릭-호석Java자바