C# 코딩테스트 강좌, 칵테일 만들기

이번 강좌에서는 ‘칵테일 만들기’라는 주제로 실제 코딩 테스트에서 자주 등장하는 문제를 다뤄보겠습니다. 이 문제는 다양한 알고리즘적 사고를 요구하며, C# 프로그래밍 언어를 통해 해결할 것입니다. 칵테일 만들기 관련 문제는 조합, 분할 정복, 최적화 문제 등 여러 가지를 포함할 수 있으며, 이 강좌에서는 특정 문제를 선정하여 단계별로 풀이하겠습니다.

문제 설명

당신에게 N가지 재료가 있습니다. 각각의 재료는 특정한 양의 알코올을 포함하고 있습니다. 또한 각각의 재료는 인덱스 1부터 N까지 부여되어 있습니다. 당신은 M (1 ≤ M ≤ N)가지의 재료를 선택하여 칵테일을 만들고자 합니다. 선택한 재료의 알코올 양의 합이 K (K는 주어진 정수)와 같아야 합니다. 당신의 목표는 다양한 조합을 찾아내어 가능한 모든 칵테일을 만들 수 있는 경우의 수를 계산하는 것입니다.

입력 형식

  • 첫 번째 줄에는 두 개의 정수 N (재료의 수), M (선택할 재료의 수)이 주어진다.
  • 두 번째 줄에는 N개의 정수로 각 재료의 알코올 양이 주어진다.
  • 세 번째 줄에는 목표하는 알코올 양 K가 주어진다.

출력 형식

가능한 칵테일 조합의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

5 3
1 2 3 4 5
5

예제 출력

5

문제 풀이 과정

이 문제를 해결하기 위해서는 여러 재료 조합을 만들고 그 조합의 알코올 합을 체크해야 합니다. C#에서 조합을 찾기 위한 방법으로는 재귀 호출을 활용할 수 있습니다. 아래는 이 문제를 해결하기 위한 기본적인 알고리즘 설계입니다.

1단계: 입력 파싱

먼저 입력된 데이터를 파싱하여 N, M, 재료의 알코올 양, K를 변수에 저장합니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        var alcohols = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int K = int.Parse(Console.ReadLine());
        
        // 향후 재귀 호출을 통해 조합을 찾아낼 것입니다.
    }
}

2단계: 조합을 찾기 위한 함수 구현

조합을 찾기 위해 재귀 함수를 구현하겠습니다. 이 함수는 매개변수로 현재 인덱스, 선택한 재료의 수와 현재까지의 알코올 양을 받을 것입니다.

static int CountCombinations(int[] alcohols, int N, int M, int K, int index, int count, int currentSum)
{
    if(count == M)
    {
        return currentSum == K ? 1 : 0;
    }
    
    if(index >= N)
    {
        return 0;
    }

    // 현재 재료를 선택하고 재귀 호출
    int includeCurrent = CountCombinations(alcohols, N, M, K, index + 1, count + 1, currentSum + alcohols[index]);
    // 현재 재료를 선택하지 않고 재귀 호출
    int excludeCurrent = CountCombinations(alcohols, N, M, K, index + 1, count, currentSum);

    return includeCurrent + excludeCurrent;
}

3단계: 메인 함수와 조합 호출

이제 메인 함수에서 위에서 정의한 조합 함수를 호출하여 결과를 출력하겠습니다. 또한, 결과를 1,000,000,007로 나누어 출력합니다.

static void Main(string[] args)
{
    var input = Console.ReadLine().Split();
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);

    var alcohols = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int K = int.Parse(Console.ReadLine());

    long result = CountCombinations(alcohols, N, M, K, 0, 0, 0);
    const int MOD = 1000000007;

    Console.WriteLine(result % MOD);
}

완전한 소스 코드

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        var alcohols = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int K = int.Parse(Console.ReadLine());

        long result = CountCombinations(alcohols, N, M, K, 0, 0, 0);
        const int MOD = 1000000007;

        Console.WriteLine(result % MOD);
    }

    static int CountCombinations(int[] alcohols, int N, int M, int K, int index, int count, int currentSum)
    {
        if(count == M)
        {
            return currentSum == K ? 1 : 0;
        }
        
        if(index >= N)
        {
            return 0;
        }

        // 현재 재료를 선택하고 재귀 호출
        int includeCurrent = CountCombinations(alcohols, N, M, K, index + 1, count + 1, currentSum + alcohols[index]);
        // 현재 재료를 선택하지 않고 재귀 호출
        int excludeCurrent = CountCombinations(alcohols, N, M, K, index + 1, count, currentSum);

        return includeCurrent + excludeCurrent;
    }
}

결론

이 알고리즘 문제는 조합과 재귀를 활용하여 간단한 접근법으로 해결할 수 있습니다. 여러 개의 재료를 조합하여 특정한 값을 만들 때 유용하게 사용할 수 있는 방식입니다. 코딩 테스트에서 자주 출제되므로 반드시 연습해보시길 권장합니다.

앞으로도 다양한 알고리즘 및 문제 해결 방식을 다룰 예정이니 많은 관심 부탁드립니다!