언제나 처음처럼

[문제 링크]

변형된 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

[문제 링크]

LCS 길이를 구하는건 이전에 풀어봤던 LCS 문제들과 같았기 때문에 쉽게 구할 수 있었다.

필자는 LCS를 출력하기 위해 pair<int, string> 형태로 값을 저장했는데 시간초과가 발생하였다.

원인은 정확히 모르겠으나 문자열 길이를 비교하기 위해 string 문자열을 매개변수로 받는 max 함수를 호출하면서 string 복사생성자와 소멸자를 많이 호출하게 되어 그만큼 시간이 늘어난 것이라 생각한다.

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

string strA, strB, strRes;
int memo[1001][1001];

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

int Length(int hereA, int hereB)
{
	if (hereA == strA.length() || hereB == strB.length())
		return 0;

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

	ret = 0;

	int same = strA[hereA] == strB[hereB]; // 같으면 1 다르면 0
	ret = max(Length(hereA + 1, hereB), max(Length(hereA, hereB + 1), Length(hereA + 1, hereB + 1) + same));

	return ret;
}

void Str(int hereA, int hereB)
{
	if (hereA == strA.length() || hereB == strB.length())
		return;

	if (strA[hereA] == strB[hereB])
	{
		strRes += strA[hereA];
		Str(hereA + 1, hereB + 1);
	}
	else if (memo[hereA + 1][hereB] >= memo[hereA][hereB + 1])
		Str(hereA + 1, hereB);
	else
		Str(hereA, hereB + 1);
}


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

	int res = Length(0, 0);
	cout << res << endl;

	if (res != 0)
	{
		Str(0, 0);
		cout << strRes << endl;
	}

	return 0;
}

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

[문제 링크]

팰린드롬인 경우는 다음과 같다.

if(S == E) 일 경우 길이가 1이므로 무조건 팰린드롬,

else if(S+1 == E && arr[S] == arr[E]) 일 경우 길이가 2며 양쪽 끝이 서로 같으므로 팰린드롬,

else if(arr[start] == arr[end] && memo[start+1][end-1] == 1) 일 경우 즉, 양쪽 끝의 숫자가 같고, 양쪽 숫자를 제외한 나머지 부분이 팰린드롬일 경우 팰린드롬이다.

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

int arr[2001], memo[2001][2001];

int Topdown(int start, int end)
{
	if (start == end) return 1;
	if (start + 1 == end) return arr[start] == arr[end] ? 1 : 0;

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

	if (arr[start] == arr[end] && Topdown(start + 1, end - 1))
		return ret = 1;
	else
		return ret = 0;
}

void Bottomup(int N)
{
	for (int i = 1; i <= N; i++)
		memo[i][i] = 1;

	for(int end = 1; end<=N; end++)
		for (int start = 1; start < end; start++)
		{
			if (start + 1 == end)
				memo[start][end] = arr[start] == arr[end] ? 1 : 0;
			else if (arr[start] == arr[end] && memo[start + 1][end - 1])
				memo[start][end] = 1;
			else
				memo[start][end] = 0;
		}
}

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

	memset(memo, -1, sizeof(memo));

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

	Bottomup(N); // 모든 경우에서 팰린드롬 여부를 미리 계산

	int M;
	cin >> M;
	while (M--)
	{
		int S, E;
		cin >> S >> E;
		cout << Topdown(S, E) << '\n';
		
		cout << memo[S][E] << '\n';
	}

	return 0;
}

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