[SW Expert Academy] 5170. 상원이의 직선 긋기 게임

5170. 상원이의 직선 긋기 게임

SW Expert Academy의 문제는 무단 복제가 금지되어있기 때문에 링크로 대체합니다!

클릭시 이동합니다!

어떻게 풀까?

가장 쉽게 떠오르는 방법은 역시 모든 점을 그려보는 것이죠!

모든 점을 그리면서 중복되는 기울기는 그리지 않는 형식으로 가면 됩니다!

그렇다면 기울기는 어떻게 체크할까요?

double을 사용해서 실수로 체크할 수도 있지만, 분모가 0이 되는 순간 처리하기가 너무 애매해집니다.

또한, 이전의 자료들을 저장하기 위해서는 set과 같은 자료구조의 힘을 빌려야하죠!

생각보다 간단하게 실수를 저장하는 방법이 있습니다!

바로, 분수 형태를 이용하는 것이죠!

2차원 배열을 사용해서 check[분자][분모] 형태로 저장하는 방법입니다!

단, 이렇게 저장할 경우에는 약간의 조절을 해줘야 합니다.

첫 번째, 1/2 , 2/4, 3/6 과 같은 기울기의 처리

분수는 수가 다르더라도 위처럼 같은 값들이 있습니다. 따라서, 실제로 체크한 배열과 그릴 수 있는 선의 갯수가 달라집니다!

하지만 이를 위해 세상의 수학에는 기약 분수라는 것이 존재합니다.

분자와 분모의 최대 공약수를 구해서 기울기의 값을 같게 만들어줍시다!

위에서 예로 들었던 1/2, 2/4, 3/6 모두 기약 분수로 나타내면 1/2 의 기울기로 저장될 것입니다!

두 번째, 분모나 분자가 0 일때의 처리

위의 경우를 봅시다!

점은 3개이고, 이 점들을 이어서 3 개의 기울기를 만들 수 있습니다.

모두 기울기가 0임에도 불구하고,

생각했던 방법으로 문제를 풀려고 하면 서로 다른 2 개의 기울기가 나타나겠죠!

이는, 부모와 자식이 바뀌어도 똑같습니다!

따라서, 부모나 자식이 0일 경우는 특정한 위치에 저장하도록 합시다! 

저같은 경우는 [0][2000]과 [2000][0]에 저장했습니다.

마지막, 음수처리는 어떻게 할 것인가?!

다행히도, 해당 문제의 x와 y의 범위는 -1000 ~ 1000입니다!

즉, 분자와 분모의 최솟값은 -2000이라는 소리죠!

원래의 값에 2000을 더해서 저장하면, 음수는 사라집니다!

하지만, 또다른 문제가 있습니다!

기울기가 -2인 경우를 생각해 봅시다!

해당 기울기는

자식 : 2, 부모 : -1

자식 : -2, 부모 : 1 로 표시할 수 있습니다.

반대로, 기울기가 2인 경우는

자식 : 2, 부모 1,

자식 : -2, 부모 : -1

두가지로 표현할 수 있죠.

따라서, 기울기의 부호에 따라서 자식과 부모의 부호를 설정해주는 조건을 넣어줍시다!

저같은 경우는 

부모의 부호는 무조건 양수로 고정하고

자식의 부호만 바뀌는 방식으로 조절했습니닷.

코드

#pragma once
#include<cstdio>
 
int GCD(int a, int b) {
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }
 
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int abs(int i1) {
    return i1 > 0 ? i1 : -i1;
}
int map[4001][4001];
int cod[200][2];
int main() {
    int t;
    
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        int n;
        scanf("%d\n", &n);
        int cnt = 0;
 
        for (int i = 0; i < n; i++) {
            scanf("%d %d\n", &cod[i][0], &cod[i][1]);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int child = cod[i][0] - cod[j][0];
                int parent = cod[i][1] - cod[j][1];
                if (parent == 0) {
                    cnt += map[0][2000] != tc;
                    map[0][2000] = tc;
                    continue;
                }
                if (child == 0) {
                    cnt += map[2000][0] != tc;
                    map[2000][0] = tc;
                    continue;
                }
                int gcd = GCD(abs(child),abs(parent));
                if (((child ^ parent) & (1 << 31))) {
                    child = -abs(child);
                    parent = abs(parent);
                }
                else {
                    child = abs(child);
                    parent = abs(parent);
                }
                cnt += map[child / gcd + 2000][parent / gcd + 2000] != tc;
                map[child / gcd + 2000][parent / gcd + 2000] = tc;
            }
        }
        
        printf("#%d %d\n", tc, cnt);
    }
    return 0;
}
 

여담

시간 복잡도는 어떻게 될까요!?

모든 점에 대해서 기울기를 구하는 시간복잡도가 가장 크기 때문에

의 시간 복잡도를 가집니다!