boj 20164: 홀수 홀릭 호석

N의 범위는 10^9-1 까지이므로 8자리까지 들어올 수 있다.

가장 큰 수가 들어오는 경우를 생각해도 8자리를 3가지 뽑는 경우는 8C3 = 56가지이고,

재귀 함수의 깊이는 그렇게 깊지 않으므로 dp를 사용하지 않아도 될 것이라고 생각했다.

 

 

풀다가 한 가지 실수해서 테스트케이스에 걸린 부분이 있는데,

length 를 구할 때, 아무 생각 없이 Math.ceil로 구해버렸다가 테스트케이스 100 이 들어오면 length = 2가 되어버린다는 것을 깨달았다...

고친 풀이는 아래와 같다.

import java.util.*;

public class Main {

	private static int max = 0;
	private static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		findAll(N, calcOdds(N));
		System.out.println(min + " " + max);
	}

	private static void findAll(int num, int odd) {
		if (num < 10) {
			max = Math.max(max, odd);
			min = Math.min(min, odd);
			return;
		}

		if (num < 100) {
			int newNum = num / 10 + num % 10;
			int newOdd = calcOdds(newNum);
			findAll(newNum, odd + newOdd);
			return;
		}

		int length = (int) Math.floor(Math.log10(num)) + 1;
		for (int firstLength = 1; firstLength <= length - 2; firstLength++) {
			for (int secondLength = 1; secondLength <= length - firstLength - 1; secondLength++) {
				int thirdLength = length - firstLength - secondLength;

				int secondPow = (int) Math.pow(10, secondLength);
				int thirdPow = (int) Math.pow(10, thirdLength);

				int firstNum = num / secondPow / thirdPow;
				int secondNum = (num / thirdPow) % secondPow;
				int thirdNum = num % thirdPow;

				int newNum = firstNum + secondNum + thirdNum;
				int newOdd = calcOdds(newNum);
				findAll(newNum, odd + newOdd);
			}
		}
	}

	private static int calcOdds(int num) {
		int sum = 0;
		while (num != 0) {
			sum += (num % 10) % 2;
			num /= 10;
		}
		return sum;
	}
}