[백준/C++] 직각삼각형 (No. 1711)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 풀 때, 처음에 잘못 생각해서 단순 반복으로 구하면 되는 문제인 줄 알았다.

실제로도 풀려서 잘 풀렸구나 싶었는데, 막상 다른 사람들의 풀이를 보니 시간이 적게 걸려서 구경했다.

 

다시보니 내 풀이가 약 561,375,500의 경우를 계산하는 풀이였었다는 걸 그 때 알았다;;

약 1500C2의 경우로 해결된다고 착각했었다..

 

다른 사람들의 풀이를 보니 시간을 조금 더 줄일 수 있는 풀이는 내적과 비율을 이용하는 방법이 있었다.

 

내적한 값이 0이 되려면 a벡터의x * b벡터의x = -a벡터의y * b벡터의y 이 성립해야한다.

 

여기서, b벡터의 x, y가 1, 3일 경우 두 벡터가 직각을 이룬다면, b벡터의 x, y가 2, 6일 경우에도 두 벡터는 직각을 이루게 된다.

 

이 처럼 벡터의 x, y 비율을 이용해 그 수를 미리 계산해 둔다면 겹치는 경우에 대해 시간을 줄일 수 있기 때문에 풀이 시간을 줄일 수 있게 된다.

 

이후 [y, x]의 벡터를 0으로 만드는 벡터는 [-y, x], [y, -x]벡터이므로 이를 찾으면 해결할 수 있다.

 

 

 

[아이디어 정리]

1. 한 점을 기준으로 다른 점들에 대해 벡터 값을 구한다.
2. 구한 벡터의 비율을 구하기 위해 최대공약수를 이용한다.
3. 전처리된 벡터들에 대해 내적을 해 직각인지 검사한다.

 

 

Code1 (전부 계산)

 

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
#include <queue>
using namespace std;

long long zz(long long t) {
	return t*t;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int N;
	cin >> N;
	vector<pair<long long, long long>> V(N);
	vector<vector<long long>> dist(N,vector<long long>(N,0));
	for (int i = 0; i < N; i++) {
		cin>>V[i].first >> V[i].second;
		for (int j = 0; j < i; j++) {
			dist[j][i]= zz(V[i].first - V[j].first) + zz(V[i].second - V[j].second);
		}
	}
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				long long a, b, c, d;
				a = dist[i][j];
				b = dist[j][k];
				c = dist[i][k];
				d = max({ a, b, c });
				if (d == a + b + c - d) {
					ans += 1;
				}
			}
		}
	}
	cout << ans;
	return 0;
}

 

 

 

Code2 (내적)

#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;


long long gcd(long long a, long long b)
{
	if (a % b == 0) {
		return b;
	}
	return gcd(b, a % b);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int N;
	cin >> N;
	vector<pair<long long, long long>> V(N);
	vector<map<pair<long long, long long>,int>> Vec(N);
	vector<vector<long long>> dist(N,vector<long long>(N,0));
	long long x, y, g;
	for (int i = 0; i < N; i++) {
		cin>>V[i].first >> V[i].second;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
		{
			if (i != j) {
				y = V[j].first - V[i].first;
				x = V[j].second - V[i].second;
				if (x == 0) {
					Vec[j][{-1, 0}] += 1;
				}
				else if (y == 0) {
					Vec[j][{0, 1}] += 1;

				}
				else
				{
					if ((x < 0 && y < 0) || (x > 0 && y > 0))
					{
						g = gcd(abs(y), abs(x));
						Vec[j][{ abs(y) / g, abs(x) / g }] += 1;
					}
					else
					{
						g = gcd(abs(y), abs(x));
						Vec[j][{ -abs(y) / g, abs(x) / g }] += 1;
					}

				}
			}
		}
	}

	int ans = 0;
	map<pair<long long, long long>, int>::iterator it;
	map<pair<long long, long long>, int>::iterator edit;

	for (int i = 0; i < N; i++) {
		for (it = Vec[i].begin(); it != Vec[i].end(); it++) {
			edit = Vec[i].find({ -it->first.second,it->first.first });
			if (edit!=Vec[i].end())
			{
				ans += edit->second * it->second;
			}
		}
	}
	cout << ans;
	return 0;
}

---

 

 

막상 내적으로 풀어보니 시간이 생각보다 오래 걸렸다;;

아무래도 map에 벡터를 넣는 과정에서 오래 걸린 것 같다.

unordered_map을 이용하면 더 빠르게 가능하겠지...?

 

https://www.acmicpc.net/problem/1711