[ SWEA 7088 ] 은기의 송아지 세기 (C++)

SWExpertAcademy의 은기의 송아지 세기(7088 / D4) 문제이다.

[ 문제풀이 ]

1) 먼저 이 문제를 각 Question이 들어올 때 마다 순차탐색으로 접근해 버린다면, 최악의 경우

   100,000 마리의 송아지를 100,000번 탐색, 즉, 100,000 x 100,000 만큼의 연산이 필요하기 때문에 시간내에 통과하기가

   힘들다.

   따라서 본인은 입력과 동시에 송아지가 몇 번Index까지 x번 송아지가 몇 마리 있는지 저장해주는 방식을 이용했다.

   본인이 저장하기 위해 사용한 배열은 int Count[][] 라는 2차원 배열인데,

   Count[a][1] = b 의 의미는 "a번 Index까지 1번품종인 송아지는 b마리 있습니다."

   Count[a][2] = b 의 의미는 "a번 Index까지 2번품종인 송아지는 b마리 있습니다."

   Count[a][3] = b 의 의미는 "a번 Index까지 3번품종인 송아지는 b마리 있습니다." 를 의미한다.

   즉, 입력과 동시에 위의 배열을 다음과 같이 저장해 주었다.

int One, Two, Three;
One = Two = Three = 0;
for (int i = 1; i <= N; i++)
{
    int a; cin >> a;
    if (a == 1) One++;
    else if (a == 2) Two++;
    else if (a == 3) Three++;
    Count[i][1] = One;
    Count[i][2] = Two;
    Count[i][3] = Three;
}

   이 후에는 질문에 맞게 송아지가 몇 마리 있는지만 출력을 해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, Q;
int Count[MAX][4];
vector<pair<int, int>> Cmd;
vector<pair<pair<int, int>, int>> Answer;
 
void Initialize()
{
    memset(Count, 0, sizeof(Count));
    Cmd.clear();
    Answer.clear();
}
 
void Input()
{
    cin >> N >> Q;
 
    int One, Two, Three;
    One = Two = Three = 0;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        if (a == 1) One++;
        else if (a == 2) Two++;
        else if (a == 3) Three++;
        Count[i][1] = One;
        Count[i][2] = Two;
        Count[i][3] = Three;
    }
 
    for(int i = 0 ; i < Q; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
void Solution()
{
    for (int i = 0; i < Q; i++)
    {
        int Start = Cmd[i].first;
        int End = Cmd[i].second;
        
        int One = Count[End][1] - Count[Start - 1][1];
        int Two = Count[End][2] - Count[Start - 1][2];
        int Three = Count[End][3] - Count[Start - 1][3];
 
        Answer.push_back(make_pair(make_pair(One, Two), Three));
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << endl;
        for (int i = 0; i < Answer.size(); i++)
        {
            cout << Answer[i].first.first << " " << Answer[i].first.second << " " << Answer[i].second << endl;
        }
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}