[C#] 백준 9375번 문제풀이

문제번호: 9375

문제명: 패션왕 신해빈

문제링크: https://www.acmicpc.net/problem/9375

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘은 해시테이블 또는 딕셔너리를 이용하여 경우의 수를 계산하는 문제를 풀어보았습니다.

사실 헤시테이블은 Non-Generic타입에 박싱, 언박싱이 일어나지만 딕셔너리는 Generic타입에 박싱/언박싱이 일어나지 않기 때문에 딕셔너리를 사용하는 것이 더 유리하고 위 문제는 Key:string, Value:int로 형식이 정해져 있지만 지금까지 헤시테이블을 한 번도 사용해보지 못해서 연습도 해볼 겸 헤시테이블을 이용한 점 양해 부탁드립니다.

 

계산공식을 구해야합니다.

옷들을 다른 조합으로 입어야 하기에 우선 같은 의상종류끼리 해시테이블에 키로 저장하고, 빈도수를 값에 저장합니다.

그 후에 빈도수를 가지고 계산을 할 건데 유의할 점이 한 가지 있습니다. 각 의상종류는 해당 종류를 안 입을 수 있는 경우의 수도 있기 때문에 각 의상종류 빈도수에 1씩 더해주고, 마지막 계산공식에 모두 다 안 입었을 경우의 수 1을 빼주어야 합니다.

 

따라서 (a+1 * b + 1...) - 1이라는 식을 구해볼 수 있습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    int t = int.Parse(Console.ReadLine());
    for (int i = 0; i < t; i++)
    {
        Hashtable hashtable = new Hashtable();

        int n = int.Parse(Console.ReadLine()); //입력 받아오기
        for (int j = 0; j < n; j++)
        {
            string[] input = Console.ReadLine().Split();

            if (hashtable.ContainsKey(input[1]))
            {
                hashtable[input[1]] = (int)hashtable[input[1]] + 1;
            }
            else
            {
                hashtable[input[1]] = 1;
            }

        }

        int answer = 1;
        foreach(var val in hashtable.Values)
        {
            answer *= (int)val + 1;
            //Console.WriteLine("더하기: " + val);
        }

        Console.WriteLine((answer-1));
    }
}