언제나 처음처럼

[문제 링크]

간단한 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

[문제 링크]

난이도 있는 타일채우기 문제였던거 같다.

점화식을 이해한다면 쉬운 문제지만 이해하기까지가 조금 까다롭다.

3XN 타일을 2칸짜리 블록(2X1, 1X2)으로 채워야하기 때문에 N이 홀수이면 채울 수 있는 경우의 수는 0이다.

또한 그림으로 3X4, 3X6 타일을 직접 그려보면 N이 2 증가할 때마다 새로운 모양으로 채우는 경우가 2개 생긴다.

따라서 점화식은 dp(N) = dp(N-2) * dp(2) + sum(dp(N-4 ~ N-(N-2)) * 2) + 2 로 나타낼 수 있다.

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

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

int memo[31];

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

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

	ret = Topdown(N - 2) * 3;
	N -= 2;

	while (N > 0)
	{
		ret += Topdown(N - 2) * 2;
		N -= 2;
	}

	return ret += 2;
}

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

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

		for (int j = 4; j <= i; j += 2)
			memo[i] += memo[i - j] * 2;
	}

	return memo[N];
}

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

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

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

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/89 동전 1의 변형 문제였다.

입력받은 동전의 가치를 배열 coin[n]에 저장할 때, k원을 만드는 동전의 최소 개수는 i = 1~n까지 k-coin[i]원을 만드는 최소 개수가 가장 작은 개수 + 1이다.

k원을 만들지 못하는 경우 -1을 출력해줘야 하기 때문에 top-down에서는 기저사례로 k가 0보다 작을 때 무한대(INF)를 반환하도록 하였고, bottom-up에서는 초기값을 무한대(INF)로 초기화하였다.

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

const int INF = 987654321;
int n, k, coin[101], memoTop[101][10000], memoBot[10000];

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

int Topdown(int start, int k)
{
	if (k <= 0) return k == 0 ? 0 : INF;

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

	ret = INF;
	for (int i = start; i <= n; i++)
		ret = min(ret, Topdown(i, k - coin[i]) + 1);

	return ret;
}

int Bottomup(int k)
{
	for (int i = 1; i <= k; i++)
	{
		memoBot[i] = INF;
		for (int j = 1; j <= n; j++)
			if (i - coin[j] >= 0)
				memoBot[i] = min(memoBot[i], memoBot[i - coin[j]] + 1);
	}
	
	return memoBot[k] == INF ? -1 : memoBot[k];
}

int main(void)
{
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> coin[i];

	// top-down
	memset(memoTop, -1, sizeof(memoTop));
	int res = Topdown(1, k);
	if (res == INF)
		cout << -1 << endl;
	else
		cout << res << endl;

	// bottom-up
	cout << Bottomup(k) << endl;

	return 0;
}

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