언제나 처음처럼

[문제 링크]

top-down으로 구현하다가 시간초과, 스택오버플로를 겪고 bottom-up으로 구현하였다.

이 문제를 N이 3일 때 까지 손으로 풀어보면 간단한 점화식을 발견할 수 있는데 점화식은 다음과 같다.

dp(N) = dp(N-1) * 2 + dp(N-2) 

점화식은 간단하지만 필자는 위 점화식이 어떻게 참이 되는지 이해를 못하였기 때문에 위 점화식이 아닌 다른 방법으로 풀었다.

핵심은 옆에 칸에 사자를 배치했느냐 안했느냐에 따라서 경우의 수가 다르다는 것이다.

#include <iostream>
using namespace std;

const int MOD = 9901;
int memo[100001][2];

int Bottomup(int N)
{
	// [i][0] : 이전칸에 배치 했을 경우
	// [i][1] : 이전칸에 배치하지 않았을 경우
	memo[1][0] = 2;
	memo[1][1] = 3;

	for (int i = 2; i <= N; i++)
	{
		memo[i][0] = (memo[i - 1][0] + memo[i - 1][1]) % MOD;
		memo[i][1] = (memo[i - 1][0] * 2 + memo[i - 1][1]) % MOD;
	}

	return memo[N][1];
}

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

	cout << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/102

내리막길 문제와 비슷한 유형의 문제였다.

(y,x)에서 (N,N)으로 가는 경우의 개수는 항상 같기 때문에 이를 메모이제이션 하면 중복을 최소화할 수 있다.

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

int N, arr[101][101];
long long memo[101][101];
int dy[2] = { 0, 1 }, dx[2] = { 1, 0 };

long long Topdown(int hereY, int hereX)
{
	if (hereY == N && hereX == N) return 1;
	if (arr[hereY][hereX] == 0) return 0;

	long long& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	int jump = arr[hereY][hereX];
	for (int i = 0; i < 2; i++)
	{
		int nextY = hereY + (dy[i] * jump);
		int nextX = hereX + (dx[i] * jump);

		if (nextY <= N && nextX <= N)
			ret += Topdown(nextY, nextX);
	}

	return ret;
}

long long Bottomup()
{
	memo[1][1] = 1;

	for(int i = 1; i<=N; i++)
		for (int j = 1; j <= N; j++)
		{
			if (arr[i][j] == 0)
				continue;

			if (i + arr[i][j] <= N)
				memo[i + arr[i][j]][j] += memo[i][j];

			if (j + arr[i][j] <= N)
				memo[i][j + arr[i][j]] += memo[i][j];
		}

	return memo[N][N];
}

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

	memset(memo, -1, sizeof(memo));
	cout << Topdown(1, 1) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup() << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 방법은 다음과 같다.

i를 0부터 N까지 반복하고 0부터 (N-i)까지의 정수 (K-1)개를 더해서 그 합이 (N-i)가 되는 경우의 수를 누적 시켜주면 된다.

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

const int MOD = 1000000000;
int memo[201][201];

int Topdown(int N, int K)
{
	if (K == 0)
	{
		if (N == 0) return 1;
		else return 0;
	}

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

	ret = 0;

	for (int i = 0; i <= N; i++)
	{
		ret += Topdown(N - i, K - 1);
		ret %= MOD;
	}

	return ret;
}

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

	for(int i=2; i<=K; i++)
		for(int j=0; j<=N; j++)
			for (int k = 0; k <= j; k++)
			{
				memo[j][i] += memo[j - k][i - 1];
				memo[j][i] %= MOD;
			}

	return memo[N][K];
}

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

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, K) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, K) << endl;

	return 0;
}

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

[문제 링크]

이 문제는 낮은 정답률에 비해 쉽게 풀 수 있었다.

정답률이 낮은 이유는 아마도 동서남북 방향을 탐색하지 않고 동쪽과 남쪽만 탐색해서 오답을 받는 경우가 많기 때문일거라 생각한다.

동서남북 방향을 탐색하여 높이가 낮은 지점이 있다면 그 지점에서 (M, N)으로 가는 경로의 개수를 구하고 그 값을 누적해주면 된다.

한 지점에서 (M, N)으로 가는 경로의 개수는 항상 같기 때문에 이를 메모이제이션해주면 중복탐색을 최소화할 수 있다.

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

int M, N, arr[501][501], memo[501][501];
int dy[4] = { 1,-1,0,0 }, dx[4] = { 0,0,1,-1 };

int Topdown(int hereY, int hereX)
{
	if (hereY > M || hereY == 0 || hereX > N || hereX == 0)
		return 0;
	if (hereY == M && hereX == N)
		return 1;

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

	ret = 0;

	for (int i = 0; i < 4; i++)
		if (arr[hereY][hereX] > arr[hereY + dy[i]][hereX + dx[i]])
			ret += Topdown(hereY + dy[i], hereX + dx[i]);

	return ret;
}

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

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

	memset(memo, -1, sizeof(memo));
	cout << Topdown(1, 1) << endl;

	return 0;
}

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

[문제 링크]

얼핏 보기엔 복잡하고 어려워보이는 문제였지만, LIS와 LDS를 구하는 dp함수를 구현하면 간단히 풀 수 있는 문제였다.

중심점 here을 기준으로 arr[1] ~ arr[here] 까지 LIS + arr[here] ~ arr[N] 까지 LDS - 1 이 바이토닉 부분 수열의 길이가 되고, 중심점 here을 1~N으로 했을 때 가장 큰 값이 문제의 정답이 된다.

#include <iostream>
using namespace std;

int N, arr[1001], LIS[1001], LDS[1001];

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

int Topdown_LIS(int here)
{
	int& ret = LIS[here];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = 1; i < here; i++)
		if (arr[i] < arr[here])
			ret = max(ret, Topdown_LIS(i) + 1);
	
	return ret;
}

int Topdown_LDS(int here)
{
	int& ret = LDS[here];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = here + 1; i <= N; i++)
		if (arr[i] < arr[here])
			ret = max(ret, Topdown_LDS(i) + 1);

	return ret;
}

int Bottomup_LIS(int here)
{
	for (int i = 1; i <= here; i++)
	{
		LIS[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[i] > arr[j])
				LIS[i] = max(LIS[i], LIS[j] + 1);
	}

	return LIS[here];
}

int Bottomup_LDS(int here)
{
	for (int i = N; i >= here; i--)
	{
		LDS[i] = 1;
		for (int j = i + 1; j <= N; j++)
			if (arr[i] > arr[j])
				LDS[i] = max(LDS[i], LDS[j] + 1);
	}

	return LDS[here];
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	// top-down
	int res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Topdown_LIS(i) + Topdown_LDS(i) - 1);
	cout << res << endl;
	
	// bottom-up
	res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Bottomup_LIS(i) + Bottomup_LDS(i) - 1);
	cout << res << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/80 LIS와 같은 유형의 문제였다.

#include <iostream>
using namespace std;

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

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

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

	ret = 1;
	for (int i = start + 1; i <= N; i++)
		if (arr[start] > arr[i])
			ret = max(ret, Topdown(i) + 1);

	return ret;
}

int Bottomup()
{
	int res = 1;
	for (int i = 1; i <= N; i++)
	{
		memo[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[i] < arr[j])
				memo[i] = max(memo[i], memo[j] + 1);
		res = max(res, memo[i]);
	}

	return res;
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	int res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	cout << Bottomup() << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/81 타일 문제와 비슷한 유형의 문제라고 생각한다.

N == 1일 때 만들 수 있는 타일은 1 한가지 존재하고,

N == 2일 때 만들 수 있는 타일은 00, 11 두가지 존재한다.

N == 3일 때 만들 수 있는 타일은 N==1일 때 만들 수 있는 타일 뒤에 N==2일 때 만들 수 있는 타일을 붙인 모양(100, 111)과 새롭게 만들 수 있는 001이 추가되어 세가지 존재하게 된다.

이를 통해 앞서 많이 풀어봤던 타일채우기 문제들과 동일한 유형의 문제임을 알 수 있다.

따라서 점화식은 다음과 같다.

dp(N) = dp(N-2) * 2 + dp(N-3)

#include <iostream>
using namespace std;

const int MOD = 15746;
int memo[1000001];

int Topdown(int N)
{
	if (N == 1) return 1;
	if (N == 2) return 2;
	if (N == 3) return 3;

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

	return ret = (Topdown(N - 2) * 2 + Topdown(N - 3)) % MOD;
}

int Bottomup(int N)
{
	memo[1] = 1;
	memo[2] = 2;
	memo[3] = 3;

	for (int i = 4; i <= N; i++)
		memo[i] = (memo[i - 2] * 2 + memo[i - 3]) % MOD;

	return memo[N];
}

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

	cout << Topdown(N) << endl;

	cout << Bottomup(N) << endl;
	
	return 0;
}

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

[문제 링크]

이항 계수를 구하는 점화식을 이용하여 쉽게 풀 수 있는 문제였다.

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

const int MOD = 10007;
int memo[1001][1001];

int Topdown(int N, int K)
{
	if (K == 1) return N;
	if (K == 0 || K == N) return 1;

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

	return ret = ((Topdown(N - 1, K - 1) % MOD) + (Topdown(N - 1, K) % MOD)) % MOD;
}

int Bottomup(int N, int K)
{
	memo[1][0] = memo[1][1] = 1;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++)
			memo[i][j] = ((memo[i - 1][j] % MOD) + (memo[i - 1][j - 1] % MOD)) % MOD;

	return memo[N][K];
}

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

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, K) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, K) << endl;

	return 0;
}

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