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

지문은 간단하게 나오지만 왜이렇게 나에게는 어려운지 모르겠다.

레이팅이 하락하여 1380(-51)을 받았다.

생각해보면 BOJ에서 공부하는 내용을 접목하는 것 보다, 뭔가 시뮬레이션쪽이 콘테스트에는 많이 나오는 것 같다.

내가 생각을 아직까지 그렇게 밖에 못해서 그런지는 잘 모르겠지만, 그냥 무작정 알고리즘으로 접근하면 정답을 찾기가 힘든 것 같다.

1번 문제는 꽤나 쉽게 풀었다.

문제 해석이 조금 어려워서 그랬지, 문제를 해석하고 나니 코딩을 하기에는 편했다.

1번 문제는 다음과 같다.

A. Football Tournament :: https://csacademy.com/contest/round-23/#task/football-tournament

3

0 2 2

1 0 1

1 2 0이 있다면

0 2 2는 1번 홈구장에서 2, 3번팀이 와서 경기를 한 것이다.

2면 1번팀이 진것, 1이면 1번팀이 홈구장에서 이긴 것인데

이 경우는 모두 1번이 진 상황이다.

1 0 1은 2번 홈구장에서 1, 3번팀이 와서 경기를 한 것인데

둘다 1이니 2번 팀이 1, 3번에게 이긴 것이다.

1 2 0은 3번 홈구장에서 1, 2번팀이 와서 경기를 하였고,

1번에게는 이기고 2번에게는 진 상황이다.

결국 가장 많이 이긴 팀을 출력해야 되는 문제이다.

범위가 2 <= N <= 100이기에 O(N^2)으로 해결 할 수 있었다.

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

2번 문제는 다익스트라로 해결하면 될 줄 알았는데 11번 Test Case에서 계속 실패하였다.

생각해보니 다익스트라로 해결하려니 모든 정점에 대해 최단거리를 구해야했고 이 문제는 쿼리까지 존재하여 O(mn^2lgN)이기에 N, M 범위가 1000이라 당연히 TLE가 났는 것이다.

B. Fast Travel :: https://csacademy.com/contest/round-23/#task/fast-travel

다른 유저에게 질문을 하다가 AC 코드를 받았다.

Greedy로 해결된다는 말에 조금 당황스럽기도 했지만, 코드를 아직 보는 눈이 부족한가 코드를 봐도 잘 모르겠다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
const int kMaxN = 1001;
 
struct Point {
    bool special;
    int x, y;
} p[kMaxN];
 
int n, travel_cost;
 
int GetDistance(int a, int b) {
    return abs(p[a].x - p[b].x) + abs(p[a].y - p[b].y);
}
 
int GetClosest(int node) {
    int where = -1;
    int mn = 1e9;
    for (int i = 1; i <= n; i += 1) {   
        if (GetDistance(i, node) < mn and p[i].special) {
            where = i;
            mn = GetDistance(i, node);
        }
    }
 
    return where;
}
 
int sol[100];
 
int Solve(int a, int b) {
    int A = GetClosest(a);
    int B = GetClosest(b);
    
    if (A == -1) {
        return GetDistance(a, b);
    }
    
    return min(GetDistance(a, b), GetDistance(a, A) + travel_cost + GetDistance(B, b));
}
 
int main() {
    cin >> n >> travel_cost;
    
    for (int i = 1; i <= n; i += 1) {
        cin >> p[i].special >> p[i].x >> p[i].y;
    }
 
    int q;
    cin >> q;
    
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << Solve(a, b) << '\n';
    }
    return 0;
}
 

더 잘 치고 싶고, 우선 영어도 더 잘하고 싶다.

레이팅에 신경쓰지 않고 계속 꾸준히 연습하여야겠다.