[백준] 20943 카톡 (C++)

카톡 문제 풀이

[백준] 20943 카톡

문제

조건

1. $N$명의 유저가 모인 특이한 오픈톡방이 있다.
2. 특이한 오픈톡방은 하나의 좌표 평면으로 구성되어 있으며, 각각 유저들은 좌표 평면 상의 서로 다른 직선 $1$개를 할당받는다.
3. 각 유저들이 서로의 톡을 보기 위해서는 각 유저들의 직선이 서로 만나야 한다. 서로 만나지 않는다면 서로의 톡을 볼 수 없다.

풀이 방식

이번 문제는 주어지는 선분의 기울기를 판단하고 그 개수를 통해서 접점이 있는 쌍의 수를 찾는 문제였다.
기울기를 키로 가지는 맵을 통해서 평행한 선분의 수를 찾고, 평행하지 않은 선분의 조합을 계산하는 방식으로 풀이 했다. 나는 2가지 부분에서 틀렸었는데 첫번째로는 이중 for문으로 시간 복잡도가 \(O(n^2)\) 이 되었던 점, 두번쨰는 만나는 선분의 짝의 수가 int 값을 넘어갈 수 있다는 점을 적용하지 않았다.
그래서 시간복잡도의 경우에는 map을 vector로 변환하여 for문 하나만으로 조합을 계산하도록 수정했다.
마지막으로 결과값의 자료형을 long long으로 수정하였다.
자세한 코드는 아래에서 확인하길 바란다.

답안

참고자료

백준 카톡 풀러가기