[C#]백준 24460번: 특별상이라도 받고 싶어

https://www.acmicpc.net/problem/24460

24460번: 특별상이라도 받고 싶어

---

• 문제

---

• 문제풀이

분할정복(divide and conquer) 알고리즘을 사용하여, 2^n 크기의 배열에서 두 번째로 작은 값을 찾는 문제를 해결하는 코드입니다.

이 문제는 큰 배열을 작은 크기의 4개의 배열로 나눈 뒤, 각각의 배열에서 두 번째로 작은 값을 찾는 과정을 반복하여 해결합니다. 따라서, 재귀함수를 사용하여 문제를 풀어나갑니다.

half는 현재 구역을 4개의 구역으로 분할하기 위해 사용되는 변수입니다. winners는 각각의 구역에서 뽑힌 사람들의 추첨번호를 저장하는 배열이며, count는 winners 배열에 저장된 사람의 수를 나타냅니다.

 

 

---

• 코드 1

using System;

class MainClass
{
    static int[][] arr;

    static int Check(int x, int y, int size)
    {
        if (size == 1)
        { 
            return arr[x][y];
        }

        int half = size / 2;
        int[] square = new int[4];
        int count = 0;

        square[count++] = Check(x, y, half);
        square[count++] = Check(x, y + half, half);
        square[count++] = Check(x + half, y, half);
        square[count++] = Check(x + half, y + half, half);

        Array.Sort(square);

        return square[1];
    }

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        arr = new int[n][];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        }

        int result = Check(0, 0, n);
        Console.WriteLine(result);
    }
}

---

• 후기

분할정복을 배웠다...!