[ SWEA 3410 ] 동서양의 경계 (C++)

SWExpertAcademy의 동서양의 경계(3410 / D5) 문제이다.

[ 문제풀이 ]

하나의 예시를 가지고 문제에 접근해보자.

.

위의 예시를 가지고 진행해보자.

지금부터, "A번열을 기준으로 선택한다" 라는 것은, "1열 ~ A번열까지(A번열 포함)를 서방지역으로, 그 나머지를 동방지역으로 간주한다" 라는 것을 의미한다.

그럼 가장 초기에, 0번열을 기준으로 선택해보자.

즉, 위의 맵에 존재하는 모든 값들은 "동방지역"이 되는 것이다.

우리가 구해야 하는 것은 "서방지역에서 나온 동방권 문화의 갯수" 와 "동방지역에서 나온 서방권 문화의 갯수" 이다.

가장 처음, 0번열을 기준으로 생각한다면, 위의 모든 값들은 "동방지역"이 되는 것이므로, 가장 초기에 우리가 구할 수 있는 값을 구해보면..

서방지역에서 나온 동방권 문화의 갯수 = 0개

동방지역에서 나온 서방권 문화의 갯수 = 4개

즉, 서로 다른 문화의 갯수의 총 갯수는 '4개'가 된다.

1번열을 기준으로 선택해보자.

그럼 위의 맵에서 '1번열'만 서방지역이 되는 것이고, 2, 3, 4열은 동방지역이 되는 것이다.

이 때의 값을 구해보면

서방지역에서 나온 동방권 문화의 갯수 = 1개

동방지역에서 나온 서방권 문화의 갯수 = 3개

이 때, 서로 다른 문화의 갯수는 총 '4개'가 된다.

기존의 결과값이였던 '4'와 차이가 없으니 그대로 넘어가보자.

2번열을 기준으로 선택해보자.

서방지역에서 나온 동방권 문화의 갯수 = 1개

동방지역에서 나온 서방권 문화의 갯수 = 1개

이 때, 서로 다른 문화의 갯수는 총 2개가 된다.

기존의 결과값이였던 '4'보다 더 작으니 값이 갱신된다.

3번열을 기준으로 선택해보자.

서방지역에서 나온 동방권 문화의 갯수 = 3개

동방지역에서 나온 서방권 문화의 갯수 = 1개

값의 갱신이 일어나질 않는다.

4번열을 기준으로 선택해보자.

서방지역에서 나온 동방권 문화의 갯수 = 4개

동방지역에서 나온 서방권 문화의 갯수 = 0개

값의 갱신이 일어나질 않는다.

위와 같은 방식으로 구하면, 2번열을 기준으로 선택했을 때, 그 차이가 가장 작아진다.

그럼, 위와 같이 "하나의 열을 기준으로" 왼쪽 열들과 오른쪽 열들을 모두 탐색하면 되는데, 이 과정을 모든 열에 대해서 하나하나 다 찾는 식으로 진행한다면, 최악의 경우 10^4 * 10^4 만큼 걸리게 되서 시간이 굉장히 타이트해지게 된다.

따라서, 본인은 단순하게 for문 하나로 해결해 주었다.

가장 처음에는(0열을 기준으로 삼았을 때) "오직 동방지역에 존재하는 서방권의 문화"만 정답에 영향을 미치게 된다".

즉, 우리는 입력과 동시에 "동방지역에 존재하는 서방권 문화의 갯수"를 Count 할 수가 있다.

그 이후, 0열에서 1열로 넘어가는 과정을 생각해보자.

1열이 동방지역 -> 서방지역으로 바뀌게 된다.

즉, 1열에 있는 'E'의 값(동방 지역의 문화)들이 "기존에 존재했던 동방 지역의 문화의 갯수"에 +가 되는 것이다.

다시한번 이야기해보자.

A열을 기준으로 삼고 계산했을 때, "서방지역이 가지고 있는 동방권 문화의 갯수가 K개" 라고 가정해보자.

이 상황에서 A + 1열은 "동방지역"에 속하는 열이였을 것이다.

이 후, A + 1열을 기준으로 삼게되면, A + 1열은 "서방지역"이 되는 것이고, "A + 1열에 있던 동방권의 문화들은, '서방지역에 있는 동방권의 문화' 들로 변경" 되어진다.

즉, K + (A + 1열에 있던 동방권 문화의 갯수) 가 A + 1열을 기준으로 삼았을 때, "서방지역이 가지고 있는 동방권 문화의 갯수" 가 되는 것이다.

반대로, 서방권 문화의 갯수는 그 만큼 감소하게 된다.

왜냐하면, A + 1열이 "동방지역"이였는데, 서방지역으로 바뀌게 되므로, 그 만큼 감소하게 된다.

이런식으로 1열부터 N열까지 진행한다면 O(N)시간만에 계산이 가능하다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 10010
using namespace std;
 
int N, M, Result, Answer;
int West_Culter[MAX];
int East_Culter[MAX];
int West_Cnt, East_Cnt;
 
int Min(int A, int B) { return A < B ? A : B ; }
 
void Initialize()
{
    Answer = 0;
    Result = 2e9;
    West_Cnt = East_Cnt = 0;
    memset(West_Culter, 0, sizeof(West_Culter));
    memset(East_Culter, 0, sizeof(East_Culter));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            char C; cin >> C;
            if (C == 'W')
            {
                West_Culter[j]++;
                West_Cnt++;
            }
            else if (C == 'E') East_Culter[j]++;
        }
    }
}
 
void Solution()
{
    Result = Min(Result, West_Cnt + East_Cnt);
    for (int i = 1; i <= N; i++)
    {
        East_Cnt = East_Cnt + East_Culter[i];
        West_Cnt = West_Cnt - West_Culter[i];
        if (West_Cnt + East_Cnt < Result)
        {
            Result = West_Cnt + East_Cnt;
            Answer = i;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << " " << Answer + 1 << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}