25682번 체스판 다시 칠하기 2, 1931번 회의실 배정

코딩테스트 : 25682번 체스판 다시 칠하기 2 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

10899

4268

3201

37.765%

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

제한

• 1 ≤ N, M ≤ 2000
• 1 ≤ K ≤ min(N, M)

using System.Data.SqlTypes;

public class BackJoon
{
    public static void Main()
    {
        int[] NMK = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int N = NMK[0];
        int M = NMK[1];
        int K = NMK[2];
        
        
        // 맞지 않으면 1, 맞으면 0 가장 적은 숫자를 골라야 함. 
        // 전체 K * K 에서 특정 색으로 시작했을 때의 경우를 빼면, 다른 색으로 시작했을 때 값이 나올까 ?
        int  [,] origin  = new int [N + 1, M + 1 ];

        // 기준 컬러, true면 흰 색 , false면 검정 색
        bool standardColor = true;

        for (int row = 1; row <= N; row++)
        {
            string rowString = Console.ReadLine();
            standardColor = !standardColor;
            bool currentColor = standardColor;
            for (int col = 1; col <= M; col++)
            {
                if (rowString[col - 1] == 'B' && currentColor
                    || rowString[col -1] == 'W' && !currentColor )
                {
                    origin[row, col] = 0;
                }
                else
                {
                    origin[row, col] = 1;
                }
                currentColor = !currentColor;
            }
        }

        int[,] sum = new int[N + 1, M + 1];
        for (int row = 1; row <= N; row++)
        {
            for (int col = 1; col <= M; col++)
            {
                // 특정 구간까지의 합을 구함. 
                sum[row, col] = sum[row - 1, col] + sum[row, col - 1] + 
                                origin[row , col] - sum[row - 1, col - 1];
            }
        }
        
        int min = int.MaxValue;

        for (int row = K; row <= N; row++)
        {
            for (int col = K; col <= M; col++)
            {
                int temp = sum[row, col] + sum[row - K, col - K]
                           - sum[row - K, col] - sum[row, col - K];
                min = Math.Min(min, temp);
                min = Math.Min(min, K*K - temp);
            }
        }
        
        Console.WriteLine(min);
        
        
    }
}

 

어제 풀었던 문제의 연장선에 있는 문제다. 

다만 다른 점은 경우의 수가 두 가지 ( 첫 블럭의 색이 검정/흰 )라는 것이다.

K * K 에서 특정 색으로 시작했을 때의 최솟값을 빼면 반대 색으로 시작했을 때의 값도 구할 수 있지 않을까 ? 

라는 생각에 일단 하나의 색 (standardColor) 를 기준으로 올바른 색이면 0, 올바른 색이 아니면 1을 배열에 넣었다. 

그 배열을 바탕으로 저번 문제에서 풀었던 것처럼 Sum[,] 배열을 선언하고 계산해 준 뒤

 

K * K 이므로 알맞게 계산을 전부 해 주면 된다. 

 

다른 사람의 흥미로운 풀이

 

반복문을 하나 줄일 수 있다. 

특정 구간까지의 합을 구하는 것을 위의 반복문과 합쳐서 계산하게 되면 조금 더 효율적으로 진행할 수 있다.

 

*  논리 연산자 '^' 는  XOR, 배타적 논리합으로 같으면 false ( 0 )  , 다르면 true ( 1 ) 을 return 한다. 

 

 

코딩테스트 : 1931번 회의실 배정  

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

248862

83763

57636

31.226%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

public class BackJoon
{
    public static void Main()
    {
        // 아이디어 : 끝나는 시간 순서대로 정렬한 뒤, 가능한게 있으면 Count +1 ,
        //없으면 다음 끝나는 시간으로 넘어감
        
        
       List<(int,int)> startEnd = new List<(int,int)>();
       int n = int.Parse(Console.ReadLine());
       for (int i = 0; i < n; i++)
       {
           int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
           startEnd.Add((arr[0], arr[1]));
       }

       startEnd.Sort ((x, y) => x.Item2.CompareTo(y.Item2));

       int currentEndTime = startEnd[0].Item2;
       int count = 1;
    
       for (int i = 0; i < startEnd.Count; i++)
       {
           int tempStartTime = startEnd[i].Item1;
           int tempEndTime = startEnd[i].Item2;
           if (currentEndTime != tempEndTime)
           {
               if (tempStartTime >= currentEndTime)
               {
                   count++;
                   currentEndTime = tempEndTime;
               }
           }
       }
       Console.WriteLine(count);
    }
}

 

87%에서 틀린 것을 보니 예외처리 문제인듯 하다. 

 

public class BackJoon
{
    public static void Main()
    {
        // 아이디어 : 끝나는 시간 순서대로 정렬한 뒤, 가능한게 있으면 Count +1 , 
        // 없으면 다음 끝나는 시간으로 넘어감
        
        
       List<(int,int)> startEnd = new List<(int,int)>();
       int n = int.Parse(Console.ReadLine());
       for (int i = 0; i < n; i++)
       {
           int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
           startEnd.Add((arr[0], arr[1]));
       }

       startEnd = startEnd.OrderBy( x => x.Item2).ThenBy(x => x.Item1).ToList();

       int currentEndTime = startEnd[0].Item2;
       int count = 1;
    
       for (int i = 1; i < startEnd.Count; i++)
       {
        int tempStartTime = startEnd[i].Item1;
        int tempEndTime = startEnd[i].Item2;

        if (tempStartTime >= currentEndTime)
        {
            count++;
            currentEndTime = tempEndTime;
        }
       }
       Console.WriteLine(count);
    }
}

 

조건 중, '시작하는 시간과 끝나는 시간이 같을 수 있다.'라는 조건을 무시했었던 문제였다.

만일 끝나는 시간으로만 정렬하고 반복문을 진행한다면 시작하는 시간과 끝나는 시간이 같은 회의를 

무시하고 지나칠 수 있는 문제가 발생한다. 따라서 시작하는 시간으로 정렬을 한 번 더 해준 다음 

시작하는 시간과 끝나는 시간이 같은 것들을 미리 더해주고 다음 회의를 진행시켜야 한다.