[백준 - C#] 13413번 오셀로 재배치

문제링크

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

13413번: 오셀로 재배치

 

문제

로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자.
○●●○○ => ○●○●○
세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.
배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
말 1개를 들어 뒤집어 놓아 색상을 변경한다.
위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다. 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다. 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 128 MB

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다.
각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다.
초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다.
흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.

 

문제정리

1. 한번에 하나의 작업만 할 수 있다.
2. 목표 상태에 도달할 수 있는 최소 횟수

이번 문제의 경우 두가지 방식으로 풀었는데, 하나는 정말 간단히 풀었고 하나는 그리디 알고리즘처럼 풀어두신 다른 블로글 참고하였습니다.

 

첫 번째는 입력받은 값과 목표로 하는 값을 하나하나 비교하여 두개가 다를 때 W와 B의 목표로 하는 값의 개수를 파악하여 비교하여 그중 큰 수를 출력해주면 되는 문제입니다.

 

두번째는 비교하는것 같으나 목표로 하는 값의 개수가 아니고 입력받은 값의 W와, B의 개수를 파악하고 반복문을 돌려 바꿀 수 있는 값이 0이 될 때까지 카운팅하고 다 더해주면 됩니다.

 

이번 문제는 그리디 알고리즘으로 어떻게 풀어야할지 감이 잡히지 않아 다른분의 풀이를 참고하였습니다.

C# 코드 - 1

        static void Main(string[] args)
        {
            StreamWriter writer = new StreamWriter(OpenStandardOutput());
            StreamReader reader = new StreamReader(OpenStandardInput());
 
            int T = int.Parse(reader.ReadLine());
 
            for (int i = 0; i < T; i++)
            {
                int N = int.Parse(reader.ReadLine());
                char[] input = reader.ReadLine().ToCharArray();
                char[] goal = reader.ReadLine().ToCharArray();
 
                int countW = 0;
                int countB = 0;
 
                for (int j = 0; j < N; j++)
                {
                    if (input[j] != goal[j]) // 입력받은 데이터와 목표로 하는 데이터가 같지 않을 경우
                    {
                        if (goal[j] == 'W') // 목표로 하는 값이 W 라면
                            countW++; // W 카운터 증가
                        else
                            countB++; // B 카운터 증가
                    }
                }
 
                // W카운터와 B 카운터 중 큰 카운터수를 출력
                writer.WriteLine((countW > countB) ? countW : countB);
            }
 
            writer.Close();
            reader.Close();
        }

 

C# 코드 - 2 ( 참고 : https://samsic.tistory.com/28 )

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int T = int.Parse(reader.ReadLine());
 
    for (int i = 0; i < T; i++)
    {
        int N = int.Parse(reader.ReadLine());
        char[] input = reader.ReadLine().ToCharArray();
        char[] goal = reader.ReadLine().ToCharArray();
 
        int countW = 0;
        int countB = 0;
 
        for (int j = 0; j < N; j++)
        {
            if (input[j] != goal[j]) // 입력받은 데이터와 목표로 하는 데이터가 같지 않을 경우
            {
                if (input[j] == 'W') // 입력받은 값이 W 라면
                    countW++; // W 카운터 증가
                else
                    countB++; // B 카운터 증가
            }
        }
 
        int count = 0;
        while (countW > 0 && countB > 0)
        {
            countW--;
            countB--;
            count++;
        }
 
        writer.WriteLine(countW + countB + count);
    }
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.