언제나 처음처럼

[문제 링크]

변형된 LIS문제였다.

필자는 길이가 i인 수열에서 i번째 원소를 반드시 포함할 때 갖는 최대값을 memo[i]에 저장하였다.

수열의 길이 N을 입력받았다면 1~N까지 위 작업을 진행한 다음 memo[1]~memo[N]에서 가장 큰 값을 찾아주면 원하는 정답을 얻을 수 있다.

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

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

int Topdown(int N)
{
	if (N == 0) return arr[N];

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

	for (int i = 0; i < N; i++)
		if (arr[i] < arr[N])
			ret = max(ret, Topdown(i) + arr[N]);
	
	return ret;
}

int Bottomup(int N)
{
	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		memo[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				memo[i] = max(memo[i], memo[j] + arr[i]);
		
		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	//top-down
	int res = 0;
	for(int i=0; i<N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

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

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

자연수 N을 제곱수의 합으로 나타낼 때 최소항의 개수를 찾는 방법은 min(1 + [N - (제곱한 값이 N보다 작거나 같은 수들의 제곱수)]의 항의 개수) 이다.

예를 들어 N = 10 일 때 최소 항의 개수는 dp[10] = min( 1 + dp[10-1], 1 + dp[10-4], 1 + dp[10-9] ) 로 나타낼 수 있다.

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

for(i = 1; i<=N; i++)

if(i*i <= N) dp[N] = min(dp[N], 1 + dp[N-i*i])

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[100001];

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

int Topdown(int N)
{
	if (N == 0) return 0;

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

	ret = INF;

	for (int i = 1; i <= N; i++)
	{
		if (i*i > N) break;
		ret = min(ret, 1 + Topdown(N - i * i));
	}

	return ret;
}

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

	for (int i = 2; i <= N; i++)
	{
		memo[i] = INF;
		for (int j = 1; j <= N; j++)
		{
			if (j*j > i) break;
			memo[i] = min(memo[i], 1 + memo[i - j * j]);
		}
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;

	cout << "top-down: " << Topdown(N) << endl;
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

top-down 방식으로 풀어보려다 너무 많은 시간을 허비한 문제였다.

동전의 순서만 다른 경우를 가려내기 위해선 2차원 dp 배열을 선언해야 하는데 dp[101][10001] 으로 선언하게 되면 메모리가 4mb를 넘게되어 메모리 초과가 발생하게 된다.

bottom-up 방식으로 풀었더니 코드도 훨씬 간결하고 쉽게 풀렸다. 

틀에 박힌 사고를 개선해야 한다는 것을 다시한번 느끼게 된 문제였다.

#include <iostream>
using namespace std;

int n, k, pay[101], memo[10001];

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

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if(j - pay[i] >= 0)
				memo[j] += memo[j - pay[i]];

	return memo[k];
}

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

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

	cout << Bottomup(k) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

시작 숫자와 자릿수를 상태값으로 가져야하기 때문에 2차원 dp 배열이 필요하다.

문제 조건을 보면 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 인정해준다고 되어있기 때문에 이를 유의하여 점화식을 세워주면 된다.

top-down 방식의 경우 시작 숫자가 i 일 때 그 뒤에 나올 수 있는 숫자는 i보다 같거나 큰 숫자이다. 따라서 시작 숫자를 i로 하고 자릿수-1을 매개변수로 넘겨주어 재귀호출하는 방법으로 풀 수 있다. 첫번째 자리에 올 수 있는 숫자는 0~9이므로 이를 다 더해주면 된다. 기저사례로 자릿수가 0일 때 끝에 도달했으므로 1을 반환한다.

bottom-up 방식의 경우 자리수가 1이고 시작 숫자가 0~9 일 때 가질 수 있는 경우의 수를 미리 저장한 다음, 임의의 수 i부터 시작하고 자리수가 N인 경우의 수는 시작 숫자가 i~9이고 자리수가 N-1인 경우의 수의 합인 것을 이용하여 값을 갱신해가면 간단하게 원하는 결과를 얻을 수 있다. 

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

int memo[10][1001];

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

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

	for (int i = start; i < 10; i++)
		ret += Topdown(i, N - 1) % 10007;

	return ret % 10007;
}

int Bottomup(int N)
{
	memset(memo, 0, sizeof(memo));

	for (int i = 0; i < 10; i++)
		memo[i][1] = 10 - i;

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

	return memo[0][N] % 10007;
}

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

	// top-down
	cout << "top-down: " << Topdown(0,N) << endl;

	// bottom-up
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

이 문제는 점화식을 세우는 과정에서 자꾸 뇌정지가 와서 오래 걸린 문제였다.

top-down 방식의 경우 사이트가 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수는 서쪽의 N번째 사이트와 동쪽의 M번째 ~ N번째 사이트가 연결되는 경우의 수들의 합이다.

기저사례로 서쪽 사이트가 1개일 때, 동쪽 사이트 개수를 반환하고, 서쪽 사이트와 동쪽 사이트 개수가 같다면 1을 반환하였다.

bottom-up 방식의 경우 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수 = 서쪽의 N번째 사이트가 동쪽의 M번째 사이트와 연결되는 경우의 수 + 동쪽의 M-1번째 사이트와 연결되는 경우의 수이며, 이를 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int memo[31][31];

//* W = 서쪽, E = 동쪽 *//
int Topdown(int W, int E)
{
	if (W == 1) return E;
	if (W == E) return 1;

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

	for (int i = 1; i <= E; i++)
		ret += Topdown(W - 1, E - i);

	return ret;
}

int Bottomup(int W, int E)
{
	for (int i = 1; i <= E; i++)
		memo[1][i] = i;

	for(int i=2; i<=W; i++)
		for (int j = i; j <= E; j++)
			memo[i][j] = memo[i-1][j-1] + memo[i][j-1];

	return memo[W][E];
}

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

		// top-down
		cout << "top-down: " << Topdown(N, M) << endl;
		// bottom-up
		cout << "bottom-up: "<< Bottomup(N, M) << endl;
	}
	return 0;
}

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

[문제 링크]

길이가 2 x n 인 스티커에서 최대 점수를 구하는 방법은 다음과 같다.

max(d[0][n], d[1][n])

즉, 마지막줄에서 위에 칸을 떼어냈을 때 얻을 수 있는 최대값 vs 마지막줄에서 아래 칸을 떼어냈을 때 얻을 수 있는 최대값 중 더 큰값이 최대 점수가 된다.

n열에서 1행을 떼어냈을 때와 2행을 떼어냈을 때 얻을 수 있는 최대값을 구하는 점화식은 다음과 같이 나타낼 수 있다.

dp(0, n) = max(dp(1, n-1) + score[0][n], dp(1, n-2) + score[0][n])

dp(1, n) = max(dp(0, n-1) + score[1][n], dp(0, n-2) + score[1][n])

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

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

int P[2][100000], memo[2][100000];

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

int Topdown(int y, int x)
{
	if (x < 0) return 0;

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

	if (y == 0) return ret = max(Topdown(1, x - 1), Topdown(1, x - 2)) + P[0][x];
	if (y == 1) return ret = max(Topdown(0, x - 1), Topdown(0, x - 2)) + P[1][x];
}

int Bottomup(int n)
{
	memo[0][0] = P[0][0];
	memo[1][0] = P[1][0];
	memo[0][1] = memo[1][0] + P[0][1];
	memo[1][1] = memo[0][0] + P[1][1];

	for (int i = 2; i < n; i++)
	{
		memo[0][i] = max(memo[1][i - 1], memo[1][i - 2]) + P[0][i];
		memo[1][i] = max(memo[0][i - 1], memo[0][i - 2]) + P[1][i];
	}

	return max(memo[0][n - 1], memo[1][n - 1]);
}
int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < n; j++)
				cin >> P[i][j];

		// top-down
		cout << "top-down: " << max(Topdown(0, n - 1), Topdown(1, n - 1)) << endl;

		// bottom-up
		cout << "bottom-up: " << Bottomup(n) << endl;
	}

	return 0;
}

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

[문제 링크]

N X M 크기의 초콜릿을 가장 적게 자르는 횟수를 구하는 공식은 (N * M - 1)이다. 이 공식을 통해서도 쉽게 정답을 구할 수 있다.

필자는 dp를 연습하기 위해 공식을 사용하지 않고 점화식을 세워서 풀었다.

N X M 크기의 초콜릿을 가장 적게 자르는 횟수는 (y축을 1~N/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1)과 (x축을 1~M/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1) 중 최솟값이다.

따라서 점화식은 다음과 같이 나타낼 수 있다.

for(i = 1; i <= N/2; i++)

dp[N][M] = max(dp[N][M], dp(i, M) + dp(N-i, M) + 1)

for(j = 1; j <= M/2; j++)

dp[N][M] = max(dp[N][M], dp(N, i) + dp(N, M-i) + 1) 

N X M 과 M X N 초콜릿은 서로 모양만 다를뿐 같은 초콜릿이기 때문에 중복을 최소화하여 효율성을 높였다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[301][301];

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

int Topdown(int y, int x)
{
	if (y == 1 || x == 1) return y == 1 ? x - 1 : y - 1;

	int& retA = memo[y][x];
	int& retB = memo[x][y];

	if (retA != 0 || retB != 0) return retA;

	int ret = INF;

	for (int i = 1; i <= y / 2; i++) // 가로로 자르기
		ret = min(ret, Topdown(i, x) + Topdown(y - i, x) + 1);

	for (int i = 1; i <= x / 2; i++) // 세로로 자르기
		ret = min(ret, Topdown(y, i) + Topdown(y, x - i) + 1);

	return retA = retB = ret;
}

int main(void)
{
	int y, x;
	cin >> y >> x;

	// top-down
	cout << Topdown(y, x) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp문제였다.

Top-down 방식으로 푸는 경우, N개의 카드를 가장 비싸게 구입하는 금액은 카드를 i개 묶음을 구입하는 금액 + N-i개의 카드를 가장 비싸게 구입하는 금액이다. 여기서 i를 1~N까지 반복하여 그 중 최대값을 구해주면 된다.

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

for(i=1; i<=N; i++)

dp(N) = max(dp[N], dp[N-i] + P[i]);

Bottom-up 방식으로 푸는 경우, 이중 for문을 통해 구현할 수 있으며 점화식은 Top-down 방식과 동일하다.

#include <iostream>
using namespace std;

int P[1001], memo[1001];

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

int Topdown(int N)
{
	if (N == 0) return 0;

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

	for (int i = 1; i <= N; i++)
		ret = max(ret, Topdown(N - i) + P[i]);

	return ret;
}

int Bottomup(int N)
{
	// memo[0] = 0 으로 초기화 해줘야 하지만 전역변수는 기본값이 0이므로 생략
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i; j++)
			memo[i] = max(memo[i], memo[i - j] + P[j]);

	return memo[N];
}

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

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

	// top-down
	cout << "Top-down: " << Topdown(N) << endl;

	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(N) << endl;

	return 0;
}

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