언제나 처음처럼

[문제 링크]

k개의 로프를 이용하여 중량이 w인 물체를 들어올릴 때  각각의 로프에는 w/k만큼의 중량이 걸린다고 한다.

k개의 로프를 이용하는 경우 들어올릴 수 있는 물체의 최대 중량은 (들 수 있는 무게가 가장 낮은 로프 * k)로 나타낼 수 있다. 

따라서, 여러개를 묶었을 때 들 수 있는 최대 중량은 들 수 있는 무게가 가장 낮은 로프에 의해 결정되기 때문에 들 수 있는 무게가 큰 로프 순으로 묶어서 중량을 계산해야 항상 최적해를 얻을 수 있다.

#include <iostream>
using namespace std;

int lope[100000];

int max(int a, int b) { return a > b ? a : b; }

void Quick_sort(int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && lope[i] >= lope[pivot])
			i++;
		while (j > start && lope[j] <= lope[pivot])
			j--;

		if (i > j)
		{
			int temp = lope[pivot];
			lope[pivot] = lope[j];
			lope[j] = temp;
		}
		else
		{
			int temp = lope[i];
			lope[i] = lope[j];
			lope[j] = temp;
		}
	}

	Quick_sort(start, j - 1);
	Quick_sort(j + 1, end);
}

int Greedy(int N)
{
	Quick_sort(0, N - 1); // 내림차순 정렬

	int ret = 0;
	for (int i = 0; i < N; i++)
		ret = max(ret, lope[i] * (i + 1));

	return ret;
}

int main(void)
{
	int N;
	cin >> N;

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

	cout << Greedy(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

https://onlytrying.tistory.com/124 동전 0 문제와 같은 유형의 문제였다.

엔화가 1, 5, 10, 50, 100, 500 단위인 것을 보면 배수로 이루어져 있다는 것을 알 수 있다.

따라서 가장 큰 금액인 500엔부터 비교하도록 구현하면 된다.

#include <iostream>
using namespace std;

int money[6] = { 500, 100, 50, 10, 5, 1 };

int Greedy(int change)
{
	int cnt = 0;

	for (int i = 0; i < 6; i++)
		if (change >= money[i])
		{
			cnt += change / money[i];
			change %= money[i];
		}

	return cnt;
}

int main(void)
{
	int price;
	cin >> price;

	cout << Greedy(1000 - price) << endl;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

알고리즘 문제 해결 전략에서도 풀어봤던 유형의 그리디 알고리즘 문제였지만 새로운 것을 알게된 문제였다.

회의가 빨리 끝나는 순으로 회의를 진행하면 항상 최적해를 얻을 수 있기 때문에 회의가 끝나는 시간을 기준으로 오름차순 정렬하여 회의를 진행하면 쉽게 정답을 얻을 수 있다.

필자는 STL algorithm 해더파일에 정의된 sort함수를 쓰지 않고 직접 퀵정렬을 구현해서 써봤는데 시간초과가 발생하였다.

문제에서 N이 최대 100,000이고 퀵정렬 최악의 시간복잡도가 O(N^2) 인 것을 고려하면 시간 초과가 뜨는 것이 이해는 갔지만 STL의 sort함수도 퀵정렬을 기반으로 동작한다고 알고 있었기 때문에 의구심이 들었다.

찾아본 결과 STL의 sort함수는 최악의 시간복잡도가 O(N^2)인 것을 보완한 특별한 정렬법을 사용한다고 한다.

https://www.acmicpc.net/board/view/16770

#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> schedule[100000];

int Greedy(int N)
{
	sort(schedule, schedule + N);

	int start = 0, ret = 0;

	for (int i = 0; i < N; i++)
	{
		if (start <= schedule[i].second)
		{
			ret++;
			start = schedule[i].first;
		}
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> schedule[i].second >> schedule[i].first;

	cout << Greedy(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

이 문제같은 경우 메모이제이션을 활용한 동적계획법으로도 정답을 얻을 수 있을 것이다.

하지만 K의 최댓값이 100,000,000이고 동전의 가치가 1원부터 시작하기 때문에 최악의 경우 시간초과가 걸릴 것이 분명하다.

문제의 핵심은 입력으로 주어지는 조건에 있다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

보다시피 Ai는 Ai-1의 배수이기 때문에 조합에 따라 K원을 만들지 못하거나, 만들 수 있는 경우로 나뉘지 않는다.

따라서, 가장 큰 가치의 동전부터 시작하여 동전의 가치가 K원보다 큰지 작은지 비교한 다음 작을 경우 K원을 동전의 가치로 나눈 몫을 동전 갯수에 누적시키고, 나머지를 가지고 다시 비교하는 것을 반복하면 최종적으로 K가 0이 되었을 때 누적된 동전 갯수가 곧 최소 갯수가 된다.

#include <iostream>
using namespace std;

int coin[10];

int Greedy(int N, int K, int cnt) // 재귀
{
	if (K == 0) return cnt;

	for (int i = N - 1; i >= 0; i--)
		if (K <= coin[i])
			return Greedy(N, K % coin[i], cnt + (K / coin[i]));
}

int Greedy2(int N, int K) // 비재귀
{
	int cnt = 0;

	for (int i = N - 1; i >= 0; i--)
	{
		if (K == 0) return cnt;

		if (K <= coin[i])
		{
			cnt += K / coin[i];
			K %= coin[i];
		}
	}

	return cnt;
}

int main(void)
{
	int N, K;
	cin >> N >> K;

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

	cout << Greedy(N, K, 0) << endl;

	cout << Greedy2(N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

간단한 그리디 알고리즘 문제였다.

인출하는데 걸리는 시간이 짧은 사람부터 먼저 인출하는 것이 항상 최적해를 보장하기 때문에, 입력받은 배열을 오름차순 정렬한 후 인출 시간이 짧은 사람부터 차례대로 계산해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <vector>
using namespace std;

void QuickSort(vector<int>& data, int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] <= data[pivot])
			i++;

		while (j > start && data[j] >= data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}

		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	QuickSort(data, start, j - 1);
	QuickSort(data, j + 1, end);
}

int Greedy(vector<int>& wait, int N)
{
	QuickSort(wait, 0, N-1);

	int time = 0, res = 0;

	for (int i = 0; i < N; i++)
	{
		time = (time + wait[i]);
		res += time;
	}

	return res;
}

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> wait;
	for (int i = 0; i < N; i++)
	{
		int P;
		cin >> P;
		wait.push_back(P);
	}

	cout << Greedy(wait, N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

변형된 LIS 문제였다. 겉으로 보기엔 LIS 문제가 아닌듯 보이지만 가장 길게 오름차순으로 서있는 아이들을 제외한 나머지 아이들을 옮겨주면 최소한의 이동으로 줄을 세울 수 있기 때문에 결과적으로 입력받은 배열의 LIS를 구한 뒤 전체 아이들 수에서 LIS를 뺀 값이 곧 정답이 된다.

#include <iostream>
using namespace std;

int N, arr[201], memo[201];

int max(int a, int b) { return a > b ? a : b; }

int LIS(int start)
{
	if (start == N) return 1;

	int& ret = memo[start];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = start + 1; i <= N; i++)
	{
		if (start == 0)
			ret = max(ret, LIS(i));
		else if (arr[start] < arr[i])
			ret = max(ret, LIS(i) + 1);
	}

	return ret;
}

int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	cout << N - LIS(0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 102 day

[문제 링크]

파보나치 수열 유형의 간단한 dp 문제였다. 문제에 제시된 조건대로 함수를 구현하면 된다.

#include <iostream>
using namespace std;

long long memo[67];

long long Topdown(int n)
{
	if (n < 2) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;

	long long& ret = memo[n];
	if (ret != 0) return ret;

	return ret = Topdown(n - 1) + Topdown(n - 2) + Topdown(n - 3) + Topdown(n - 4);
}

long long Bottomup(int n)
{
	memo[0] = memo[1] = 1;
	memo[2] = 2, memo[3] = 4;

	for (int i = 4; i <= n; i++)
		memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3] + memo[i - 4];

	return memo[n];
}

int main(void)
{
	int tc;
	cin >> tc;
	
	while (tc--)
	{
		int n;
		cin >> n;

		cout << Topdown(n) << endl;

		cout << Bottomup(n) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 101 day

[문제 링크]

O로 표시된 칸이 없을 경우 (첫번째 칸 -> N*M번째 칸 으로 가는 경우의 수) 를 구해주면 되고,

O로 표시된 칸이 있을 경우 (첫번째 칸 -> O로 표시된 칸으로 가는 경우의 수) * (O로 표시된 칸 -> N*M번째 칸으로 가는 경우의 수) 를 구해주면 된다.

#include <iostream>
using namespace std;

int N, M, K, memo[15*15][15*15];

int Topdown(int start, int end)
{
	if (start >= end) return start == end ? 1 : 0;

	int& ret = memo[start][end];
	if (ret != 0) return ret;

	if(start%M != 0)
		ret += Topdown(start + 1, end);

	ret += Topdown(start + M, end);

	return ret;
}

int main(void)
{
	cin >> N >> M >> K;

	if (K == 0)
		cout << Topdown(1, N*M) << endl;
	else
		cout << Topdown(1, K) * Topdown(K, N*M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 100 day