[Csacademy] Csacademy Round #22 (Div. 2 only) 이야기

오늘은 Csacademy라는 사이트에서 처음으로 콘테스트를 치뤘다.

문제 자체는 상당히 쉬웠지만, 왜인지 모르게 혼자 헛짓거리하는 시간이 너무 많았다.(코딩을 짬뽕처럼 해버렸다.)

Codeforces에 비해 문제는 매우 쉬운 편이었고, UI도 깔끔해서 접근하기는 코포에 비해 좋았다.

3번문제까지 풀 수 있었지만, 3번 문제는 더이상 메모이제이션을 할 방법을 찾지 못해 결국 풀지 못하였다.

(마지막 Test Case에서 계속 TLE를 받았다.)

더 잘하고 싶고, 더 많이 풀어보고 싶었지만 아직 많이 모자란 것 같아 내심 아쉬웠다.

오늘 1번 문제는 다음과 같다.

A. Triangle Count :: https://csacademy.com/contest/archive/#task/triangle-count

말할 것도 없이 매우 쉬운 문제였다.

삼각형 성립 조건은 세 변의 길이를 알 때 작은 변 두개의 합이 큰 변보다 크면 된다.

따라서 정렬을 한번 하여 작은 변부터 찾을 수 있도록 한 뒤, 3중 for문으로 해결할 수 있는 문제였다.  

이 문제는 O(N^3)으로 해결하였다. (N의 범위가 최대 100이기에)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int main() {     int n;     int arr[101];       scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       sort(arr, arr + n);       int cnt = 0;       for (int i = 0; i < n-2; i++)     {         for (int j = i + 1; j < n-1; j++)         {             for (int k = j + 1; k < n; k++)             {                 int t1, t2, t3;                   t1 = arr[i];                 t2 = arr[j];                 t3 = arr[k];                   if (t1 + t2 > t3)                     cnt++;             }         }     }       printf("%d", cnt);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

두번째 문제가 오늘 나의 속을 썩였다.

B. Frequency Exception :: https://csacademy.com/contest/archive/#task/frequency-exception

일단 처음부터 해석을 잘못하고 들어가서 멍청하게 W/A를 받았다.

나는 이 문제를 보고 총 몇가지의 수가 출현하느냐? 라고 묻는지 알았지만, 

그것이 아닌 다른 수들과 달리 다른 빈도로 출현하는 수가 뭐냐? 를 묻는 문제였다.

일단, array로 할 지 map으로 할 지 판단하기 위해 수의 범위를 보니 10^9이었다.

따라서 배열에는 모두 담아내어 O(1)로 해결할 수 없었기에 map을 이용하여 O(lgN)으로 접근하였다.

정말 매우 기분 나쁜 코드이지만, 현재로서는 더이상 코드를 다듬을 자신이 없다.

문제가 쉬웠는데 답을 잘 못찾고 있는 것에 대해 매우 실망스러웠다.

해결 과정 ::

1. 일단 map에 모든 수의 빈도를 담아둔다.

2. 가장 작은 수의 빈도 수를 처음 가져온다.

3. map을 순회하면서 처음 가져온 빈도 수와 다른 빈도 수가 나타나면 

처음 빈도 수, 현재 빈도 수, 그 다음 빈도 수를 이용하여 해결한다.

4. 처음 빈도 수를 1, 현재 빈도 수를 2, 다음 빈도 수를 3이라 하면 1과 3이 같으면 2가 정답이고

2와 3이 같으면 1이 정답이다. 

아래 코드에는 1과 2가 같으면 3이 정답이라는 else구문이 있는데 매우 쓰레기 코드이다.

이미 if문에서 1과 2가 다를 때 if문에 접근을 하였는데 무슨 생각인지 멍청한 것 같다. 결국 else 구문은 없어도 된다.

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
map<int, int> m;
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        m[val]++;
    }
 
    int firstVal = m.begin()->second;
    int firstPos = m.begin()->first;
 
    for (auto it = m.begin(); it != m.end(); it++)
    {
        // 가장 처음 본 빈도수와 다를 경우
        if (it->second != firstVal)
        {
            int secondPos = it->first;
            int secondVal = it->second;
 
            it++;
            if (it == m.end())
            {
                printf("%d", secondPos);
                break;
            }
 
            else
            {
                int thirdPos = it->first;
                int thirdVal = it->second;
 
                // 1이랑 3이랑 같냐
                if (thirdVal == firstVal)
                {
                    printf("%d", secondPos);
                    break;
                }
 
                // 2랑 3이랑 같냐
                else if (thirdVal == secondVal)
                {
                    printf("%d", firstPos);
                    break;
                }
 
                // 1이랑 2랑 같냐
                else
                {
                    printf("%d", thirdPos);
                    break;
                }
            }
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

마지막 내가 푼 3번 문제는 매우 아쉬움이 많이 남는 문제이다.

C. Black Shapes :: https://csacademy.com/contest/round-22/#task/black-shapes

백준 알고리즘 사이트에서 흔히 볼 수 있을 법한 문제인데, 잘 해결해내지 못하였는게 너무 아쉽다.

이 문제는 단순히 BFS 응용문제인 듯 하였다.(콘테스트 후 정답 코드를 봐도 BFS로 풀고 있긴 했다.)

문제 자체는 0과 1로 구성된 2차원 배열이 있을 때 1로만의 연속된 최대 넓이 혹은 어떤 0중 하나만을 1로 바꾸면 연속된(상, 하, 좌, 우로) 최대 넓이를 구할 수 있을 까라는 문제였다. 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef struct _INFO_
{
    int y;
    int x;
    int crash;
}INFO;
 
typedef pair<int, int> pii;
 
int map[1002][1002];
int visit[1002][1002];
int visitNum = 1;
queue<INFO> q;
 
int n, m;
int getCnt;
 
void bfs(int i, int j, int t)
{
    q.push(INFO{ i, j, t });
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int crash = q.front().crash;
 
        q.pop();
 
        if (visit[y][x] == visitNum || (map[y][x] == 0 && crash == 1))
            continue;
 
        visit[y][x] = visitNum;
        getCnt++;
 
        if (y + 1 < n && map[y + 1][x] == 1 && visit[y + 1][x] != visitNum)
            q.push(INFO{ y + 1, x, 0 });
 
        if (y - 1 >= 0 && map[y - 1][x] == 1 && visit[y - 1][x] != visitNum)
            q.push(INFO{ y - 1, x, 0 });
 
        if (x + 1 < m && map[y][x + 1] == 1 && visit[y][x + 1] != visitNum)
            q.push(INFO{ y, x + 1, 0 });
 
        if (x - 1 >= 0 && map[y][x - 1] == 1 && visit[y][x - 1] != visitNum)
            q.push(INFO{ y, x - 1, 0 });
 
 
        if (crash == 0)
        {
            if (y + 1 < n && map[y + 1][x] == 0 && visit[y + 1][x] != visitNum)
                q.push(INFO{ y + 1,x, 1 });
 
            if (y - 1 >= 0 && map[y - 1][x] == 0 && visit[y - 1][x] != visitNum)
                q.push(INFO{ y - 1 ,x, 1 });
 
            if (x + 1 < m && map[y][x + 1] == 0 && visit[y][x + 1] != visitNum)
                q.push(INFO{ y, x + 1, 1 });
 
            if (x - 1 >= 0 && map[y][x - 1] == 0 && visit[y][x - 1] != visitNum)
                q.push(INFO{ y,x - 1, 1 });
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%1d", &map[i][j]);
 
    int cnt = 0;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (visit[i][j] == visitNum || (map[i][j] == 1 && visit[i][j] >= 1))
                continue;
 
            if (map[i][j] == 0)
                visitNum++;
 
            bfs(i, j, 0);
 
            cnt = max(cnt, getCnt);
            getCnt = 0;
        }
    }
 
    printf("%d", cnt);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

BFS로 풀어내니 18번 테스트케이스에서 시간 초과가 났다.

디버깅 결과 중복해서 넓이를 또 구하는 행위를 하고 있어 메모이제이션을 적절하게 하지 못한 것이었다.

BFS에서는 나름 완벽하게 이해하고 적용할 수 있다 생각했지만, 아직 많이 모자란 부분이 있다는 것을 많이 느꼈다.

이번 시험을 계기로 어려운 문제들도 많이 접해서 다음 콘테스트에서는 더 좋은 성적으로 돌아오고 싶다.