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

안녕하세요.

플젝 스케줄에 치이면서 백준풀이를 약 2달간 안 하다가 프로젝트 3개가 잘 마무리되어 다시 시작해보려 합니다.

다시 시작할 겸 이제부터는 문제 해설 대신 개인적인 문제 풀이과정과 이에 대해 더욱 솔직하고 집중적으로 글을 써보려고 합니다.

그럼 시작해보겠습니다.

 

문제번호: 2275

문제명: 부녀회장이 될 테야

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

 

해당 문제를 처음 봤을 때는 계산 공식을 찾아야겠다는 생각이 들었습니다.

직접 a-1 층의 b호까지의 사람 수 합을 하나하나 다 구해서 더하여 풀이하는 것은 비효율적이라고 생각했기 때문에 공식을 찾으려 시도해 보았습니다. 문제 태그에 '수학'이 있어서도 이유가 되겠네요. 저는 주로 어떠한 문제의 계산 공식을 찾으려 할 때는 직접 테스트케이스를 메모장에 적어보며 생각합니다.

 

메모장에 특정 호실에 거주중인 사람수를 적어보았다.

 

하지만 제 생각이 부족했던 탓인지 진짜 공식이 없는 것인지 이렇게 해서 공식을 찾진 못했습니다.

그래서 그냥 정직하게 for문으로 문제를 풀어보려 합니다.

제한시간이 0.5초이긴 하지만 실제 입력 제한은 14 미만으로 연산량이 크지 않다는 것을 확인했습니다.

 

그렇게 총 5중 반복문으로 코드를 작성하였습니다.

하지만 너무나 당연하게도 테스트케이스를 처음으로 입력하여 테스트하니 정답과 전혀 다른 값이 출력되었습니다.

문제를 찾아보니, 제가 인덱스 범위를 한 줄에서 잘못 설정했다는 것을 깨닫게 되었습니다.

해당 인덱스 범위를 고치고 다시 테스트해 보았더니 또 정답과 다른 값이 출력되었습니다.

 

그렇게 한참을 헤매다가 반복문에서 인덱스 값이 1씩 밀리고 있다는 것을 발견했습니다.

문제의 의도대로라면 1부터 시작해야 했던 값을 0부터 시작하고 있었기 때문입니다.

해당 문제를 고치고 다시 테스트해 보았더니 드디어 올바른 값이 나오게 되었습니다.

 

저는 이번문제풀이 경험을 바탕으로 다이내믹 프로그래밍 기법을 더욱 적극적으로 이용해야겠다는 생각을 하게 되었습니다.

기능별로 나누어져 있는 코드가 디버깅하기에 더욱 용이할 것 같았기 때문입니다.

 

다음은 정답코드입니다.

public static void Main()
{
    int T = int.Parse(Console.ReadLine());
    for (int i = 0;  i < T; i++)
    {
        int k = int.Parse(Console.ReadLine()); // K 층
        int n = int.Parse(Console.ReadLine()); // N 호

        int[,] pcArray = new int[k + 1,n + 1];

        // 0층 초기화
        for (int m = 1; m <= n; m++)
            pcArray[0, m] = m;

        // 1층부터 k층까지
        for (int j = 1; j <= k; j++)
        {
            for (int m = 1; m <= n; m++)
            {
                pcArray[j, m] = 0;
                for (int l = 1; l <= m; l++)
                    pcArray[j, m] += pcArray[j - 1, l];
            }
        }


        Console.WriteLine(pcArray[k,n]);
    }
}