[백준] 20164번 : 홀수 홀릭 호석 - 자바[Java]

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

20164번: 홀수 홀릭 호석

풀이

위 문제는 다음과 같은 연산을 반복한다.

• 입력받은 숫자 -> 홀수 개수 카운트
• 숫자를 짜름 -> 짜른 각각의 숫자를 모두 더한 숫자 -> 홀수 개수 카운트한 다음 이전 카운트에 더함

숫자의 홀수 개수를 카운트한 다음 이전 카운트에 더하는 로직이 반복되므로, 재귀호출 또는 반복문을 사용해야 한다. 또한 만들 수 있는 모든 경우의 수를 구해 그중 최솟값과 최댓값을 구해야 한다.

즉, 재귀호출을 사용하며 모든 경우의 수를 구할 수 있는 DFS를 사용하였다.

DFS를 사용하여 모든 경우의 수를 구하기 때문에, 최솟값과 최댓값은 static 전역 변수에 따로 저장하도록 했다.

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

먼저 입력받은 문자를 숫자로 변환한 후 cutNumber()를 호출해 DFS를 시작한다.

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        cutNumber(n, 0);
        
        System.out.println(min + " " + max);
    }

 

void cutNumber(int n, int cnt): 숫자 n으로 문제의 연산을 수행한다. DFS를 사용하여 모든 경우의 수를 구한다.

    private static void cutNumber(int n, int cnt) {
    	cnt += countOddNumber(n);
    	
    	if (n / 10 == 0) {
    		min = Integer.min(min, cnt);
    		max = Integer.max(max, cnt);
    	}
    	else if (n / 100 == 0) {
    		int next = n / 10;
    		next += n % 10;
    		cutNumber(next, cnt);
    	}
    	else {
    		String str = String.valueOf(n);
    		for (int i = 0; i < str.length() - 2; i++) {
    			for (int j = i+1; j < str.length() - 1; j++) {
    				int next = Integer.parseInt(str.substring(0, i+1));
    				next += Integer.parseInt(str.substring(i+1, j+1));
    				next += Integer.parseInt(str.substring(j+1));
    				
    				cutNumber(next, cnt);
    			}
    		}
    	}
    }

countOddNumber()를 수행하여 숫자 n에서 홀수의 개수를 찾는다.

그 다음 수가 한 자리인 경우, 두 자리인 경우, 세 자리인 경우에 따라 다르게 처리한다.

한 자리인 경우 최종값을 구했으므로 min과 max 값을 각각 업데이트한다.

두 자리인 경우 2개로 나눠서 합을 구하여 새로운 수를 구하고 cutNumber()를 호출한다.

세 자리인 경우 이중 for문을 사용하여 끊을 수 있는 모든 임의의 위치에 대해 3개의 수로 분할하고, 3개를 더한 값을 새로운 수를 구한 다음 cutNumber()를 호출한다.

 

int countOddNumber(int n): 숫자 n에 포함된 홀수의 개수를 구한다.

    private static int countOddNumber(int n) {
    	int cnt = 0;
    	while (n > 0) {
    		int tmp = n % 10;
    		if (tmp % 2 == 1) {
    			cnt++;
    		}
    		n /= 10;
    	}
    	return cnt;
    }

 

전체 코드

import java.io.*;

public class Main {
	
	private static int min = Integer.MAX_VALUE;
	private static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        cutNumber(n, 0);
        
        System.out.println(min + " " + max);
    }
    
    private static void cutNumber(int n, int cnt) {
    	cnt += countOddNumber(n);
    	
    	if (n / 10 == 0) {
    		min = Integer.min(min, cnt);
    		max = Integer.max(max, cnt);
    	}
    	else if (n / 100 == 0) {
    		int next = n / 10;
    		next += n % 10;
    		cutNumber(next, cnt);
    	}
    	else {
    		String str = String.valueOf(n);
    		for (int i = 0; i < str.length() - 2; i++) {
    			for (int j = i+1; j < str.length() - 1; j++) {
    				int next = Integer.parseInt(str.substring(0, i+1));
    				next += Integer.parseInt(str.substring(i+1, j+1));
    				next += Integer.parseInt(str.substring(j+1));
    				
    				cutNumber(next, cnt);
    			}
    		}
    	}
    }
    
    private static int countOddNumber(int n) {
    	int cnt = 0;
    	while (n > 0) {
    		int tmp = n % 10;
    		if (tmp % 2 == 1) {
    			cnt++;
    		}
    		n /= 10;
    	}
    	return cnt;
    }
}