[백준/JAVA] 20164번: 홀수 홀릭 호석

📖 문제

20164번: 홀수 홀릭 호석

 

 

💡  풀이 방식

• 재귀, 브루트포스

재귀 함수의 인자로 (현재 숫자, 여태껏 나온 홀수의 갯수)를 갖는다.

 

[1] 재귀 함수 cut(int num, int total)

1. 한 자리 숫자인 경우, 여지껏 나온 홀수의 갯수와 최솟값 최댓값을 비교해 갱신한다.

2. 두 자리 숫자인 경우, 두 숫자를 분해한다. (재귀 함수 사용)

3. 세 자리 이상의 숫자인 경우, 완전탐색을 통해 해당 숫자를 3등분할 인덱스 2개를 구한다.

그리고 나서 해당 인덱스들에서 잘랐을 때 나오는 합과 홀수의 갯수를 갱신해 숫자가 한 자리 숫자가 될 때까지 분해하러 간다. (재귀)

 

[2] 홀수 갯수 구하는 함수 getOdd(int num)

해당 숫자 num이 0이 되기 전까지 10씩 나누며 분해해 홀수 갯수를 구한다.

 

 

 

💥 유의사항

3자리 이상인 수를 3등분으로 자르는 모든 경우의 수

→ 완전탐색( 2중 for문 )으로 경우의 수 만들 수 있음!

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        cut(N, getOdd(N));
        System.out.println(min + " " + max);
    }
    
    // 재귀
    private 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();
            
            // 브루트포스로 숫자 3등분하기 (i는 자르는 점1, j는 자르는 점2의 위치)
            for(int i = 0 ; i < len - 2 ; i++) {
                for(int j = i + 1 ; j < len - 1 ; 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));
                }
            }
        }
    }
    
    // 홀수 갯수 구하는 함수
    private static int getOdd(int num) {
        int cnt = 0;
        
        while(num > 0) {
            int cur = num % 10;
            
            if(cur % 2 == 1)    cnt++;
            num /= 10;
        }
        
        return cnt;
    }
}

 

---

💦 어려웠던 점

- 재귀 쓸 생각은 했는데 숫자가 3개 이상인 경우 처리를 어찌할지 몰랐다.

- dfs로 자를 점의 위치 2개를 구할 생각을 하였는데, 그럴 필요 없이 그냥 브루트포스로 점 2개 위치를 잡아주면 되는 것이었다!!

- getOdd 메소드 사용할 생각을 하지 못 했다,,

 

1회독	2회독	3회독	4회독	5회독
V	240626

 

 

(+240626 2회독 16212KB, 164ms)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        dfs(N, getOdd(N));
        System.out.println(min + " " + max);
    }
    
    private static void dfs(int num, int result) {
        if(num < 10) {    // 한 자리 숫자인 경우 
            min = Math.min(min, result);
            max = Math.max(max, result);
        }
        else if(num < 100) {    // 두 자리 숫자인 경우
            int sum = (num/10) + (num%10);
            dfs(sum, result + getOdd(sum));
        }
        else {    // 세 자리 이상 숫자인 경우
            String str = Integer.toString(num);
            int len = str.length();
            
            for (int i = 0; i < len - 2; i++) {    // 자를 점 위치1 
                for (int j = i + 1; j < len - 1; j++) {    // 자를 점 위치2 
 
                    String s1 = str.substring(0, i+1);
                    String s2 = str.substring(i+1, j+1);
                    String s3 = str.substring(j+1);
                    
                    int sum = Integer.parseInt(s1) + Integer.parseInt(s2) + Integer.parseInt(s3);
                    dfs(sum, result + getOdd(sum));
                }
            }
        }
    }
    
    // 숫자에서 홀수 갯수 구하는 함수
    private static int getOdd(int x) {
        int cnt = 0;
        
        while(x > 0) {            
            if((x % 10) % 2 == 1
                cnt++;
 
            x /= 10;
        }
        
        return cnt;
    }
}
 

---

(참고)

백준 20164 홀수 홀릭 호석(Java,자바)

[ BOJ ][JAVA][20164] 홀수 홀릭 호석