[알고리즘 문제 풀기] 홀수 홀릭 호석(20164)

1. 문제 풀이 아이디어

• 숫자를 한 자리, 두 자리, 세 자리 이상으로 나누어 재귀적으로 합을 구하며, 홀수의 개수를 세어 최소 및 최대 값을 갱신하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int max = int.MinValue;
    int min = int.MaxValue;
    int n = int.Parse(sr.ReadLine());
    HashSet<int> set = new HashSet<int>();
    Solve(n, 0);
    sw.WriteLine($"{min} {max}");

    void Solve(int num, int count)
    {
        if (num < 10)
        {
            if (num % 2 == 1) count++;
            max = Math.Max(max, count);
            min = Math.Min(min, count);
            return;
        }
        List<int> list = new List<int>();
        while (num > 0)
        {
            int a = num % 10;
            if (a % 2 == 1) count++;
            list.Insert(0, a);
            num /= 10;
        }
        if (list.Count == 2)
        {
            Solve(list[0] + list[1], count);
            return;
        }
        for (int i = 1; i < list.Count - 1; i++)
        {
            for (int j = i + 1; j < list.Count; j++)
            {
                int a = 0;
                for (int k = 0; k < i; k++)
                {
                    a *= 10;
                    a += list[k];
                }
                int b = 0;
                for (int k = i; k < j; k++)
                {
                    b *= 10;
                    b += list[k];
                }
                int c = 0;
                for (int k = j; k < list.Count; k++)
                {
                    c *= 10;
                    c += list[k];
                }
                Solve(a + b + c, count);
            }
        }
    }
}

3. 정리

• Solve(num, count) 함수는 현재 숫자와 홀수 개수를 인자로 받아 최소, 최대 값을 갱신한다.

• 숫자가 한 자리일 경우 홀수 여부를 확인한 후 min과 max 값을 갱신한다.

• 숫자를 자릿수별로 리스트에 저장하고, 두 자리일 경우 단순한 합으로 재귀 호출한다.

• 세 자리 이상일 경우 가능한 모든 분할 조합을 생성하여 합을 구한 후 재귀적으로 Solve 함수를 호출한다.

• 모든 경우를 탐색한 후 min과 max 값을 출력한다.