굳건하게

문제 : https://www.acmicpc.net/problem/9372

[알고리즘풀이]

음... 문제가 읽다 보면 정말 이상한 문제라는 걸 캐치할 수 있습니다.

연결된 그래프가 입력으로 주어지므로 당연히 모든 도시를 여행할 수 있고, 가중치가 모두 1이므로 그냥 우리는 도시가 N개면 (N - 1)번의 비행으로 모든 도시를 방문할 수 있습니다.

문제의 의도를 모르겠네요...

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while(t--){
		int n, m;
		cin >> n >> m;
        for(int i = 0; i < m; i++){
            int x, y;
            cin >> x>> y;
        }
        cout << n-1 << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/14490

[알고리즘풀이]

1. 문자열로 입력받아, ':' 를 기준으로 숫자 2개(a, b)를 따로 저장한다.

2. 숫자 a, b는 최대 input이 100,000,000 이므로 최대 50,000,000을 공약수로 가질 수 있다.

따라서, 2부터 50,000,000가지 순회하며 공약수면 a, b를 계속 나눠준다.

#include<iostream>
#include<cmath>
#include<vector>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string I, temp = {};
	cin >> I;
	int a,b, i = 0;
	while (I[i] != ':') {
		temp += I[i];
		i++;
	}
	a = stoi(temp);
	
	i++;
	string temp2 = {};
	while (i < I.size()) {
		temp2 += I[i];
		i++;
	}
	b = stoi(temp2);

	for (int i = 2; i < 50000001; i++) {
		if (a % i == 0 && b % i == 0) {
			while ((a % i == 0) && (b % i == 0)) {
				a /= i;
				b /= i;
			}
		}
	}
	cout << a << ':' << b;
}

문제 : https://www.acmicpc.net/problem/2303

[알고리즘풀이]

k번 째 사람마다 5개의 카드가 들어오면 모든 경우에 대해서 3중 for문으로 계산해보고 최대값과 k를 같이 저장한다. 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int, int>> M;

int main(void) {
	int t, N[5];
	cin >> t;
	for (int k = 1; k <= t; k++) {
		for (int i = 0; i < 5; i++)
			cin >> N[i];
		int m = -1;
		for (int i = 0; i < 5; i++) {
			for (int j = i + 1; j < 5; j++) {
				for (int k = j + 1; k < 5; k++) {
					m = max(m, (N[i] + N[j] + N[k]) % 10);
				}
			}
		}
		M.push_back(make_pair(m, k));
	}
	sort(M.begin(), M.end());
	cout << M[t - 1].second;
}

문제 : https://www.acmicpc.net/problem/2162

[알고리즘풀이]

선분이 입력되면 그 전까지 입력된 모든 선분들을 순회하며, 두 선분이 교차하는지 CCW를 이용해서 체크해주고

교차한다면 같은 그룹에 Union-find를 이용해 Union 해준다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n, P[3000];
int c[3000];

vector<pair<pair<int, int>, pair<int, int>>> point;

int CCW(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	int temp1 = (b.second - a.second) * (c.first - a.first) + a.second * (b.first - a.first);
	int temp2 = (b.first - a.first) * c.second;

	if (temp1 < temp2) // 반시계
		return 1;
	else if (temp1 > temp2) // 시계
		return -1;
	else // 일직선
		return 0;
}

int isIntersect(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> d) {
	int ab = CCW(a, b, c) * CCW(a, b, d);
	int cd = CCW(c, d, a) * CCW(c, d, b);
	if (ab == 0 && cd == 0) {
		if (a > b)swap(a, b);
		if (c > d)swap(c, d);
		return c <= b && a <= d;
	}
	return ab <= 0 && cd <= 0;
}

int find(int x) {
	if (P[x] == x)
		return x;
	return P[x] = find(P[x]);
}

void merge(int x, int y) {
	int P_a = find(x);
	int P_b = find(y);
	P[P_a] = P_b;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		P[i] = i;

	int z = n;
	int j = 0;
	while (n--) {
		pair<int, int> a, b;
		cin >> a.first >> a.second >> b.first >> b.second;

		for (int i = 0; i < j; i++) {
			pair<int, int> c = point[i].first;
			pair<int, int> d = point[i].second;
			if (isIntersect(a, b, c, d)) {
				merge(i, j);
			}
		}
		point.push_back(make_pair(a, b));
		j++;
	}
	int count = 0;
	for (int i = 0; i < j; i++) {
		if (c[find(i)]++ == 0)
			count++;
	}	
	int m = -1;
	for (int i = 0; i < j; i++) {
		m = max(m , c[i]);
	}
	cout << count << '\n' << m << endl;
}