[BAEKJOON] 백준 28238: 정보 선생님의 야망 (C#)

문제 링크

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

 

 

문제

송도고의 정보 선생님, 박상진 선생님은 송도고를 코딩을 좋아하는 친구라면 누구든지 들어오고 싶어 하는 명성이 자자한 학교로 만들고자 하는 야망이 있다.

박상진 선생님은 이를 위해 주 2회로 진행되는 알고리즘 특강을 개설하려 한다. 알고리즘 특강을 듣고자 하는 학생은 총 𝑛명이며, 각 학생은 월요일부터 금요일까지의 순서대로 각 요일의 수업 참가 가능 여부를 제출하였다. 각 학생은 2번의 특강에 모두 참가할 수 있어야 특강을 수강할 수 있다.

박상진 선생님을 도와 특강 일정을 어떻게 정해야 최대한 많은 학생이 알고리즘 특강을 수강할 수 있는지 구하는 프로그램을 작성하여라.

 

 

입력

첫 번째 줄에 알고리즘 특강을 듣고자 하는 학생의 수 𝑛이 주어진다.

두 번째 줄부터 𝑛개의 줄에 걸쳐 각 𝑖+1번째 줄에 𝑖번째 학생의 요일별 참가 가능 여부를 의미하는 다섯 개의 정수 𝑎𝑖,1,…,𝑎𝑖,5가 공백으로 구분되어 순서대로 주어진다. 각 정수는 0 또는 1이며, 월요일부터 금요일까지의 순서대로 1이면 학생 𝑖가 해당 요일에 참가할 수 있음을, 0이면 참가할 수 없음을 의미한다.

 

 

출력

첫 번째 줄에 특강을 들을 수 있는 학생의 수의 최댓값을 출력한다.

두 번째 줄에 정수 다섯 개를 공백으로 구분하여 출력한다. 각 정수는 0 또는 1이어야 하며, 다섯 개의 정수 중 세 개는 0, 두 개는 1이어야 한다. 이는 월요일부터 금요일까지의 순서대로 1이면 특강을 하는 날, 0이면 특강을 하지 않는 날로 결정했을 때 수강할 수 있는 학생의 수가 최대임을 의미한다. 가능한 특강 일정이 여러 가지인 경우 그중 아무것이나 출력하면 된다.

 

 

제한

•  1≤𝑛≤106.
•  1≤𝑖≤𝑛,1≤𝑗≤5에 대해 𝑎𝑖,𝑗는 0 또는 1이다.

 

 

 

통과한 답안

namespace _28238
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[,] attend = new int[n, 5];

            for (int i = 0; i < n; i++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                for (int j = 0; j < 5; j++)
                {
                    attend[i, j] = int.Parse(inputs[j]);
                }
            }

            int maxStudents = 0;
            int[] bestDays = new int[5];

            for (int d1 = 0; d1 < 4; d1++)
            {
                for (int d2 = d1 + 1; d2 < 5; d2++)
                {
                    int cnt = 0;
                    for (int i = 0; i < n; i++)
                    {
                        if (attend[i, d1] == 1 && attend[i, d2] == 1)
                        {
                            cnt++;
                        }
                    }
                    if (cnt > maxStudents)
                    {
                        maxStudents = cnt;
                        bestDays = new int[5];
                        bestDays[d1] = 1;
                        bestDays[d2] = 1;
                    }
                }
            }

            Console.WriteLine(maxStudents);
            if (maxStudents == 0)
            {
                Console.WriteLine("0 1 1 0 0");
            }
            else
            {
                Console.WriteLine(string.Join(" ", bestDays));
            }
        }
    }
}

 

학생의 수와 그 학생이 참석할 수 있는 요일이 matrix 구조로 주어질 때,

두 번 참석할 수 있는 가장 많은 학생의 수와 그 요일을 찾는 문제이다.

 

우선 이 matrix 구조를 받아오기 위해서 2차원 배열을 이용하여 아래와 같이 받아왔다.

int[,] attend = new int[n, 5];
for (int i = 0; i < n; i++)
{
    string[] inputs = Console.ReadLine().Split(' ');
    for (int j = 0; j < 5; j++)
    {
        attend[i, j] = int.Parse(inputs[j]);
    }
}

 

이후에 이 문제를 푸는데 사용한 로직은

가능한 두 요일의 조합(월,화 / 월,수 / 월,목 / ... / 수,목 / 수,금 / 목,금)을 

모두 조사하여 학생의 수가 가장 큰 값을 찾도록 구현하였다.

 

이중 for 문을 사용하여 d1, d2를 가지고 둘 다 참석할 수 있는 학생의 수를 구하고,

이 수가 최대 참석할 수 있는 학생의 수보다 크다면 그를 갱신하도록 구현하였다.

 

마지막으로 위의 경우에서 최대 학생의 수가 0인 경우에도 아무것이나 출력해야하므로

if문을 이용하여 아래와 같이 예외를 만들었다.

if (maxStudents == 0)
{
    Console.WriteLine("0 1 1 0 0");
}