굳건하게

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

[알고리즘풀이]

1 ~ N 일까지 급여가 있을 때, 우리는 조건에 의해 최대 M일 동안 연속해서 일해야한다.

무식하게 O(N^2)으로 풀 수도 있지만, 다음과 같이 알고리즘을 설계하면 O(N)으로 손쉽게 풀 수 있는 문제다.

먼저, 우리는 최대 이익을 원하므로 M일 동안 모두 일해야한다.

따라서, 1 ~ M일까지의 급여의 합(tmp)을 구해 초기값으로 설정한다.

그 후, tmp 에 N[M + 1] 을 더하고, N[1] 을 빼면, 2 ~ M + 1일까지의 급여의 합이 되고,

갱신된 tmp에 N[M + 2] 를 더하고, N[2] 을 빼면, 3 ~ M + 2일까지의 급여의 합이 된다.

이 과정을 반복하며 가장 큰 값을 찾으면 된다.

#include<iostream>
#include<algorithm>

using namespace std;

long long n, m, N[100001];

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> N[i];
	}

	long long ans = 0, tmp = 0;
	for (int i = 1; i <= m; i++)
		tmp += N[i];

	ans = tmp;
	for (int i = m + 1; i <= n; i++){
		tmp = tmp + N[i] - N[i - m];
		ans = max(ans, tmp);
	}

	cout << ans;
}

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

[알고리즘풀이]

먼저, 피보나치에 관한 수학적 정리를 이용해야 문제를 해결할 수 있습니다.

gcd(a,b) = g 라고 했을 때, gcd( fibonacci(a), fibonacci(b) ) = fibonacci(g) 이다.

즉, a번 째 피보나치 수와 b번 째 피보나치 수의 최대공약수는 a, b의 최대공약수번 째 피보나치 수와 같습니다.

이 정리를 이용해, 우리는 fibonacci(gcd(a,b)) 를 구하면 됩니다.

gcd(a,b) 는 유클리드 호제법을 이용해서 빠르게 구할 수 있고,

fibonacci(gcd(a,b))는 행렬의 곱셈을 이용해서 문제를 해결할 수 있습니다.

( 유사 문제 풀이 : https://travelbeeee.tistory.com/92?category=817856 )

#include<iostream>

#define m 1000000007
#define ll long long

using namespace std;

ll a,b, fib_n, fib_m, ta, tb;

ll gcd(ll a, ll b) {
	if (b > a) {
		ll t = a;
		a = b;
		b = t;
	}
	while (b) {
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> a >> b;
	ll GCD = gcd(a, b);

	ll M[2][2] = { {1,1},{1,0} };
	ll A[2][2] = { {1,0},{0,1} };
	ta = GCD - 1;
	while (ta) {
		if (ta % 2 == 1) {
			// A * M 을 A에 갱신.
			ll temp[2][2] = {};
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					// A[i][j] = A[i][j] * M[i][j];
					for (int k = 0; k < 2; k++) {
						temp[i][j] += ( M[i][k] * A[k][j] ) % m;
					}
				}
			}
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 2; j++)
					A[i][j] = temp[i][j];
		}
		// M * M을 갱신.
		ll temp[2][2] = {};
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				// M[i][j] = M[i][j] * M[i][j];
				for (int k = 0; k < 2; k++) {
					temp[i][j] += (M[i][k] * M[k][j]) % m;
				}
			}
		}
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				M[i][j] = temp[i][j];
		ta /= 2;
	}
	cout << A[0][0] % m;
}

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

[알고리즘풀이]

Union - Find 를 이용해서 문제를 해결했습니다.

( 대부분 DFS, BFS로 문제를 푸셨더라고요....!! DFS, BFS 풀이는 다른 분들 블로그 참고하시면 될 것 같습니다. )

n : 도시의 크기를 나타내는 수 ( n * n : 도시의 크기 )

N[x][y] : 현재 도시별 인구가 담겨있는 배열.

1) 번호 부여.

(i , j) 도시의 번호 = i * n + j 로 정의하면, 모든 도시에게 0 ~ (n * n - 1)까지 번호를 하나씩 부여할 수 있습니다.

2) Union - find

(0, 0)부터 (n-1, n-1)까지 모든 도시에게 번호를 부여한 후, 1차원 배열로 Union - find 를 진행합니다.

N[i][j] 와 N[k][l] 이 인접해있고, 두 도시의 인구 차이가 L 보다 크거나 같고, R 보다 작거나 같으면 (i , j) 와 (k, l)을 Union(Merge) 해줍니다.

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n - 1; j++)
				if (check(abs(N[i][j] - N[i][j + 1]))) {
					merge(i * n + j, i * n + (j + 1));
					stop++;
				}

		for (int j = 0; j < n; j++)
			for (int i = 0; i < n - 1; i++)
				if (check(abs(N[i][j] - N[i + 1][j]))) {
					merge(i * n + j, (i + 1) * n + j);
					stop++;
				}

3) 도시 인구 초기화.

조건에 해당되서 Union된 도시가 있다면, 인구 이동을 진행해야 합니다.

각 도시별로 root 값을 다 find 한 후, 같은 root 값을 가지는 도시들은 하나의 vector에 Push합니다.

		vector<int> g[2500];
		for (int i = 0; i < n * n; i++){
			g[find(i)].push_back(i);
		}

이제 root 값이 같은 도시들은 모두 하나의 vector에 들어가 있습니다.

따라서,  size가 0 보다 큰 모든 vector 들(root 값이 같은 도시가 있는 도시들)을 하나씩 순회하며 인구를 초기화해주면 됩니다.

		for (int i = 0; i < n * n; i++) {
			int cnt = g[i].size();
			if (cnt > 0) {
				int sum = 0;
				for (int j = 0; j < g[i].size(); j++) {
					sum += N[g[i][j] / n][g[i][j] % n];
				}
				int avg = sum / cnt;
				for (int j = 0; j < g[i].size(); j++) {
					N[g[i][j] / n][g[i][j] % n] = avg;
				}
			}
		}

4) 최종 코드

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

using namespace std;

int n, l, r, N[50][50];
int p[2500] = {};
int h[2500] = {};
int f[2500] = {};

bool check(int a) {
	if (l <= a && a <= r)
		return true;
	return false;
}

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

void merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y)
		return;

	if (h[x] < h[y])
		p[x] = y;
	else {
		p[y] = x;
		if (h[x] == h[y])
			h[x]++;
	}
	return;
}

int main(void) {
	cin >> n >> l >> r;

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

	int c = 0;

	while (1) {
		for (int i = 0; i < n * n; i++) {
			p[i] = i;
			h[i] = 0;
		}

		int stop = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n - 1; j++)
				if (check(abs(N[i][j] - N[i][j + 1]))) {
					merge(i * n + j, i * n + (j + 1));
					stop++;
				}

		for (int j = 0; j < n; j++)
			for (int i = 0; i < n - 1; i++)
				if (check(abs(N[i][j] - N[i + 1][j]))) {
					merge(i * n + j, (i + 1) * n + j);
					stop++;
				}
		if (stop == 0)
			break;

		vector<int> g[2500];
		for (int i = 0; i < n * n; i++){
			g[find(i)].push_back(i);
		}

		for (int i = 0; i < n * n; i++) {
			int cnt = g[i].size();
			if (cnt > 0) {
				int sum = 0;
				for (int j = 0; j < g[i].size(); j++) {
					sum += N[g[i][j] / n][g[i][j] % n];
				}
				int avg = sum / cnt;
				for (int j = 0; j < g[i].size(); j++) {
					N[g[i][j] / n][g[i][j] % n] = avg;
				}
			}
		}
		c++;
	}
	cout << c;
}

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

[알고리즘풀이]

두 배열 A, B를 합친 후 정렬해서 출력해야되는 문제입니다.

따라서, 그냥 A, B를 구별하지말고 하나로 입력 받아서 정렬한 후 출력하면 됩니다.

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

using namespace std;

int N, M;
vector<int> v;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N + M; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < N + M; i++)
		cout << v[i] << ' ';
}