[알고리즘 문제 풀기] 222-풀링(17829)

1. 문제 풀이 아이디어

• 재귀적으로 배열의 크기를 줄여가면 문제를 해결할 수 있다.

2. 나의 정답 코드

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
int n = int.Parse(sr.ReadLine());
int[,] nn = new int[n, n];
for (int i = 0; i < n; i++)
{
    string[] split = sr.ReadLine().Split();
    for (int j = 0; j < n; j++)
    {
        nn[i, j] = int.Parse(split[j]);
    }
}
sw.WriteLine(solve(nn));

sw.Close();
sr.Close();
int solve(int[,] arr)
{
    int n2 = arr.GetLength(0);
    if (n2 == 2)
    {
        return getSecond(arr[0, 0], arr[0, 1], arr[1, 0], arr[1, 1]);
    }
    int[,] arr2 = new int[n2 / 2, n2 / 2];
    for (int i = 0; i < n2; i += 2)
    {
        for (int j = 0; j < n2; j += 2)
        {
            arr2[i / 2, j / 2] = getSecond(arr[i, j], arr[i, j + 1], arr[i + 1, j], arr[i + 1, j + 1]);
        }
    }
    return solve(arr2);
}
int getSecond(int a, int b, int c, int d)
{
    int[] arr = { a, b, c, d };
    Array.Sort(arr);
    return arr[2];
}

3. 정리

• solve() 함수는 배열을 입력받아 2x2 블록 단위로 줄여나가며 새로운 배열을 생성한다.

• 배열 크기가 2 x 2가 되면 getSecond()를 호출하여 최종 결과를 반환한다.

• getSecond() 함수는 4개의 값을 정렬하여 두 번째로 큰 값을 반환한다.

• 이 과정을 반복하여 배열 크기가 줄어들면서 최종적으로 하나의 값이 남게 된다.