백준 20164 홀수홀릭호석 (JAVA)

문제

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

20164번: 홀수 홀릭 호석

코드

package com.company;

import java.util.Scanner;

public class Main {

    static String N;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int temp = 0;

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

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

    private static void divide(String input) {
        //길이가 3이상일경우
        if (input.length() >= 3) {
            for (int i = 1; i < input.length() - 1; i++) {
                for (int j = i + 1; j < input.length(); j++) {
                    //3개의 수로 분할
                    String a = input.substring(0, i);
                    String b = input.substring(i, j);
                    String c = input.substring(j);

                    //각 수의 홀수 개수 계산
                    temp += calc(a);
                    temp += calc(b);
                    temp += calc(c);

                    divide(String.valueOf(Integer.parseInt(a) + Integer.parseInt(b) + Integer.parseInt(c)));
                    //더한것 되돌리기
                    temp -= calc(a);
                    temp -= calc(b);
                    temp -= calc(c);
                }
            }
        }

        //길이가 2일 경우
        else if (input.length() == 2) {
            //각 수의 홀수 개수 계산
            temp += input.charAt(0) % 2;
            temp += input.charAt(1) % 2;

            divide(String.valueOf(Integer.parseInt(String.valueOf(input.charAt(0))) + Integer.parseInt(String.valueOf(input.charAt(1)))));
            //이전 함수로 돌아가기전에 더한 것 되돌리기
            temp -= input.charAt(0) % 2;
            temp -= input.charAt(1) % 2;
        }

        //길이가 1일 경우
        else if (input.length() == 1) {
            //홀수 인지 아닌지 계산
            temp += Integer.parseInt(input) % 2;

            max = Math.max(temp, max);
            min = Math.min(temp, min);

            //이전 함수로 돌아가기전에 더한 것 되돌리기
            temp -= Integer.parseInt(input) % 2;
            return;
        }
    }

    private static int calc(String number) {
        int count = 0;
        for (int i = 0; i < number.length(); i++) {
            if (number.charAt(i) % 2 != 0) {
                count++;
            }
        }

        return count;
    }
}

풀이

눈으로만 풀면 상당히 난해하다고 느낄수도 있는 문제이다. 그러나 손으로 직접 그려가면서 천천히 풀어나가면 쉽게 해결할수 있는 문제이다.

우선 문제에서 제시한 조건에 대해서 차례대로 하나씩 코드를 작성해준다. 나 같은 경우에는 수의 자리수가 1일 경우, 2일 경우 3일 경우로 나누어서 해결하였다. 또한 수의 자리수가 2이상일 경우에는 한번 더 분할해야하기 때문에 재귀문으로 작성하였다.

또한 자르고 난뒤 임시로 만든 변수에 각 자리수가 홀수냐 아니냐를 판단해주어서 홀수가 맞다면 +1 아니면 그냥 넘어간다. 그렇게 계속해서 분할 할 수 없을때까지 함수를 진행한다. 그러다 자리수가 1이면 현재 수가 홀수인지 아닌지를 파악한 후 지금까지 더해온 변수와 MAX값과 MIN값과 비교를 하며 갱신을 한다.

여기서 중요한 점은 함수의 호출을 완료하였다면 현재 자리수의 홀수값을 구해줘서 더해줬던것을 빼서 다시 원상태로 복구해야한다는 점이다. 해당 작업을 해주지않으면 분할을 다르게 하는 상황에서도 홀수의 개수는 계속해서 누적이 되는 문제가 생기고 만약 홀수의 개수를 0으로 초기화를 해버린다면 함수의 호출이 있기 전까지 세고 있었던 홀수의 개수를 날려버리는 상황이 생긴다.