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

오늘은 코드 포스 포함해서 최초로 c번 문제를 풀었는 날이다.

레이팅은 1413(+50)으로 마무리 하였다.

A번 문제를 빠르게 풀고 B번 문제를 빠르게 풀었다고 생각했지만, B번에서 9번의 W/A와 함께 이번 시험도 물건너갔다고 생각했다.

하지만 C, D번을 한번 훌터보았는데 C는 안봐도 늘 출제되는 BFS 유형에 점으로 움직이는것이 아닌 도형(사각형)으로 움직이는 것이었다.

D번은 LIS의 느낌이 많이 나면서 최종적으로 구해진 LIS에서 작업을 해주면 될 것 같았다.

물론 D번은 B번에 시간을 너무 많이 쏟아 풀지는 못했지만, 남은 시간동안 C번을 풀어보기로 하고, C번을 풀었다.

그리고 2번의 W/A를 통해 작은 코딩 실수가 있는 2부분을 해결하면서 콘테스트를 참가하는 동안 처음으로 C번을 A/C를 받았다.

A번 문제는 항상 쉽게 나오는 것 같다.

A. 0-Sum Array :: https://csacademy.com/contest/round-25/#task/0-sum-array

배열에서 하나의 수를 제외하고 모든 수를 더한 후, 제외한 수를 -1을 곱하여 더하면 0이 되는 수를 찾아야 한다.

5
1 3 -5 3 4

여기서는 

1 -5 3 4를 다더하면 3이고 빼놓은 3을 -3하면 합이 0이 된다.

이 문제의 핵심은 결국

그냥 배열의 모든 수를 다 더하고, 0번 Index부터 보면서 -val*2를 하여 합이 0이되면 그 값의 인덱스가 답이다.

시간 복잡도 O(N)

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

B번은 마지막에 틀린 테스트 케이스를 보고 한줄을 작성하지 않은 것을 깨닫고 난 후 이미 후회해도 늦었지만, 

시험이 끝나고 문제를 해결하였다.

B. Suspect Interval :: https://csacademy.com/contest/round-25/#task/suspect-interval

문제 내용은 다음과 같다.

1~100000 사이의 값이 존재한다.

배열에는 그사이 값이 들어가게 되고 [A,B]라는 내용이 주어진다.

[A,B]의 조건은, A와 B사이의 간격을 의미하는데 이때, A와 B사이에 배열값 하나만 들어가야 한다.

예를들어

3
200 10 5

인 경우 5~200사이 10값 하나만 가지고 간다면, [6, 199]가 되어 194가 간격이고

여기서 정답은 10~100000사이 200값 하나만 가지고 가는 것을 하여, 100000 -11 + 1을 한 99990이 답이다.

시간 복잡도 O(N)

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int arr[100010];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    sort(arr, arr + n);
 
    int get = 0;
 
    // x, y, z수가 있다면 ()사이에 있는것이 포함되는 수
    for (int i = 0; i < n; i++)
    {
        // [(x), y>
        get = max(get, (arr[i + 1] - 1) - (arr[i]) + 1);
        // <x, (y), z>
        get = max(get, (arr[i + 2] - 1) - (arr[i] + 1) + 1);
    }
 
    // [1, (x)]
    get = max(get, arr[0]);
    // [1, (x), y>
    get = max(get, arr[1] - 1 - 1 + 1);
    // <x, (y), 100000]
    get = max(get, 100000 - (arr[n - 2] + 1) + 1);
    // [(y), 100000]
    get = max(get, 100000 - arr[n - 1] + 1);
 
    printf("%d", get);
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

get = max(get, arr[1] - 1 - 1 + 1);

이 부분을 하나 빼먹고 계속 고민하다보니 문제를 결국 풀지 못했었다.

C번은 BFS 문제이나, 응용된 문제이다.

보통 BFS문제는 좌표를 가지고 움직이지만, 이번 문제는 사각형이라는 도형을 가지고 BFS를 해야한다.

C. Rectangle Path :: https://csacademy.com/contest/round-25/#task/rectangle-path

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

예제로 바로 생각해보자

4 5
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
2 2 1 1 1 4

이렇게 총 7번을 움직인 것이다.(1은 장애물이므로 건들면 안된다.)

BFS로 똑같이 풀되, 아래로 갈때는 아래축의 x좌표들이 새로운 점과 만날때 1이 있는지 검사,

왼쪽으로 갈때는 왼쪽축의 y좌표들이 새로운 점과 만날때 1이 있는지 검사... 이런 식으로 해주면 된다.

(정확한 시간복잡도를 생각하지 못하겠다)

#include <iostream>
#include <queue>
#include <cstdio>
 
using namespace std;
 
int arr[1010][1010];
int visit[1010][1010];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &arr[i][j]);
 
    int h, w, sr, sc, fr, fc;
    scanf("%d %d %d %d %d %d", &h, &w, &sr, &sc, &fr, &fc);
 
    h--;
    w--;
 
    queue<pair<pair<int, int>, int>> q;
 
    q.push({ { sr,sc }, 0 });
 
    while (!q.empty())
    {
        int hereY = q.front().first.first;
        int hereX = q.front().first.second;
        int cnt = q.front().second;
 
        q.pop();
    
        if (visit[hereY][hereX])
            continue;
 
        visit[hereY][hereX] = 1;
 
        if (hereY == fr && hereX == fc)
        {
            printf("%d", cnt);
            return 0;
        }
 
        bool chk = true;
        if (hereY + 1 <= n && hereY + 1 + h <= n && !visit[hereY + 1][hereX])
        {
            for (int i = hereX; i <= hereX + w; i++)
                if (arr[hereY + 1 + h][i] == 1)
                {
                    chk = false;
                    break;
                }
 
            if (chk)
                q.push({ { hereY + 1,hereX }, cnt + 1 });
        }
 
        chk = true;
        if (hereY - 1 > 0 && !visit[hereY - 1][hereX])
        {
            for (int i = hereX; i <= hereX + w; i++)
                if (arr[hereY - 1][i] == 1)
                {
                    chk = false;
                    break;
                }
 
            if (chk)
                q.push({ { hereY - 1, hereX }, cnt + 1 });
        }
 
        chk = true;
        if (hereX + 1 <= m && hereX + 1 + w <= m && !visit[hereY][hereX + 1])
        {
            for (int i = hereY; i <= hereY + h; i++)
                if (arr[i][hereX + 1 + w] == 1)
                {
                    chk = false;
                    break;
                }
 
            if (chk)
                q.push({ { hereY, hereX + 1 }, cnt + 1 });
        }
 
        chk = true;
        if (hereX - 1 > 0 && !visit[hereY][hereX - 1])
        {
            for (int i = hereY; i <= hereY + h; i++)
                if (arr[i][hereX - 1] == 1)
                {
                    chk = false;
                    break;
                }
 
            if (chk)
                q.push({ { hereY, hereX - 1 }, cnt + 1 });
        }
    }
 
    printf("-1");
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>