언제나 처음처럼

[문제 링크]

먹는데 가장 오래걸리는 도시락을 먼저 데우고 먹기 시작해야 가장 빨리 점심시간을 마칠 수 있다.

따라서, 먹는데 걸리는 시간을 기준으로 내림차순 정렬한 다음 오래 걸리는 도시락 순으로 데우도록 구현하였다.

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

vector<pair<int, int>> lunchBox;

int Greedy(int N)
{
	// 먹는데 오래걸리는 순으로 정렬
	sort(lunchBox.begin(), lunchBox.end(), greater<pair<int, int>>());

	int longest = 0, time = 0;

	for (int i = 0; i < N; i++)
	{
		if (longest < lunchBox[i].first + lunchBox[i].second)
		{
			longest = lunchBox[i].first;
			time += lunchBox[i].second;
		}
		else
		{
			longest -= lunchBox[i].second;
			time += lunchBox[i].second;
		}
	}

	return time + longest;
}

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

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

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

		for (int i = 0; i < N; i++)
			lunchBox.push_back(make_pair(eat[i], heat[i]));

		cout << Greedy(N) << endl;

		lunchBox.clear();
	}

	return 0;
}

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

[문제 링크]

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

러시아팀의 한 선수를 이길 수 있는 한국팀의 선수가 여러명 있을 때 가장 레이팅이 낮은 선수를 매칭시켜야만 최대의 승점을 얻을 수 있기 때문에 이를 그대로 구현하였다.

먼저 러시아팀, 한국팀의 선수들을 레이팅에 따라 오름차순으로 정렬한다.

러시아팀에서 레이팅이 가장 낮은 선수를 시작으로 한국팀에서 레이팅이 가장 낮은 선수부터 비교한다.

한국팀 선수가 러시아팀 선수보다 레이팅이 같거나 클경우 두 선수를 매치 시키고 러시아팀의 다음 선수를 비교한다.

한국팀에서 가장 레이팅이 높은 선수까지 탐색했다면 더이상 비교할 필요가 없기 때문에 누적한 승점을 반환한다.

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

vector<int> rusia, korea;

int Greedy(int N)
{
	// 오름차순 정렬
	sort(rusia.begin(), rusia.end());
	sort(korea.begin(), korea.end());

	int lowest = 0, win = 0;

	for (int i = 0; i < N; i++)
		if (rusia[lowest] <= korea[i])
		{
			lowest++;
			win++;
		}

	return win;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			rusia.push_back(rate);
		}

		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			korea.push_back(rate);
		}

		cout << Greedy(N) << endl;

		rusia.clear();
		korea.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 107 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

[문제 링크]

간단한 dp 문제였다.

현재 계산하려는 위치와, 누적한 값에 따른 올바른 등식의 개수를 2차원 dp배열에 저장하여 중복을 최소화하였다.

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

int N, arr[101];
long long memo[101][21];

long long Topdown(int here, int sum)
{
	if (sum < 0 || sum > 20) return 0;
	if (here == N) return sum == arr[N] ? 1 : 0;

	long long& ret = memo[here][sum];
	if (ret != -1) return ret;

	ret = 0;

	ret += Topdown(here + 1, sum + arr[here]);
	ret += Topdown(here + 1, sum - arr[here]);

	return ret;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	cin >> N;

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

	cout << Topdown(2, arr[1]) << endl;

	return 0;
}

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

[문제 링크]

먼저 N x M 행렬과 M x K 행렬을 곱하면 N x K 행렬이 만들어진다는 것을 알고있어야 한다.

행렬 A, B, C, D가 있을 때 만들 수 있는 곱셈 순서는 다음과 같다.

(A) * (BCD),

(AB) * (CD),

(ABC) * (D)

2개로 묶인 행렬은 바로 곱해주면 되지만 3개 이상으로 묶인 행렬은 그 최솟값을 구하기 위해 다시 곱셈 순서를 나눠줘야 한다.

예를 들어 (A) * (BCD) 에서 (BCD)를 (B) * (CD) 와 (BC) * (D) 두가지로 나눌 수 있다.

위 과정을 재귀적으로 반복하는 함수를 구현하면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
int proc[501][2], memo[501][501];

int min(int a, int b) { return a < b ? a : b; }

int Topdown(int start, int end)
{
	if (start == end) return 0;
	if (start + 1 == end) return proc[start][0] * proc[start][1] * proc[end][1];

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

	ret = INF;

	for (int i = start; i < end; i++)
		ret = min(ret, Topdown(start, i) + Topdown(i + 1, end) + proc[start][0] * proc[i + 1][0] * proc[end][1]);

	return ret;
}

int Bottomup(int start, int end)
{
	for(int i = 1; i <= end; i++)
		for (int j = i - 1; j > 0; j--)
		{
			memo[j][i] = INF;

			for(int k=j; k<i; k++)
				memo[j][i] = min(memo[j][i], memo[j][k] + memo[k + 1][i] + proc[j][0] * proc[k + 1][0] * proc[i][1]);
		}

	return memo[start][end];
}

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

	cout << Topdown(1, N) << endl;

	cout << Bottomup(1, N) << endl;

	return 0;
}

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

[문제 링크]

암호를 해석하는 경우의 수를 구하는 방법은 다음과 같다.

1) 첫번째 자리 숫자가 0이면 암호를 해석할 수 없다.

2) 첫번째 자리 숫자가 1~9 일 때, 이 숫자를 알파벳으로 바꾼 다음 두번째 자리 숫자를 첫번째 자리로 했을 때 만들 수 있는 암호의 수

3) 첫번째 자리와 두번째 자리 숫자가 10~26 일 때 이 숫자를 알파벳으로 바꾼 다음 세번째 자리 숫자를 첫번째 자리로 했을 때 만들 수 있는 암호의 수

따라서, 암호를 해석하는 경우의 수는 2번 + 3번이 되며, 이를 탑다운 방식으로 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int MOD = 1000000;
int memo[5000];
string str;

int Topdown(int start)
{
	if (start == str.length()) return 1;

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

	ret = 0;

	if (str[start] != '0')
	{
		ret += Topdown(start + 1);

		if (start + 1 < str.length() && (str[start] - '0') * 10 + (str[start + 1] - '0') <= 26)
			ret += Topdown(start + 2);
	}

	return ret %= MOD;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	cin >> str;

	cout << Topdown(0) << endl;

	return 0;
}

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