언제나 처음처럼

[문제 링크]

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

[문제 링크]

지난번에 완전탐색으로 한번 풀었던 문제였는데 이번에 동적 계획법을 사용하여 다시 풀게되었다.

아래에서 위로 탐색하는 알고리즘은 금방 생각해냈지만, 위에서 아래로 탐색하여 정답을 얻어내는 알고리즘을 생각하다가 이틀이나 날려먹었다.....

일단은 아래에서 위로 재귀호출을 통해 탐색하는 방식으로 문제를 해결하였다.

이 문제의 핵심은 해당 일에 상담을 했을 때 얻는 최대이익과 상담을 하지 않았을 때 얻는 최대이익 중 더 큰 값을 선택한다는 것에 있다.

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

dp(N) = max(dp(N+1), dp(N+T[N]) + P[N]);

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int N, T[16], P[16], memo[16];
inline int max(int a, int b) { return a > b ? a : b; }

int brute(int start, int pay)
{
	int ret = pay;
	for (int i = start; i < N; i++)
	{
		int next = i + T[i];
		if (next > N) continue;
		ret = max(ret, brute(next, pay + P[i]));
	}
	return ret;
}

int Topdown(int start)
{
	if (start >= N) return start == N ? 0 : -INF;

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

	return ret = max(Topdown(start + 1), Topdown(start + T[start]) + P[start]);
}

int main(void)
{
	cin >> N;

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

	// brute-force
	cout << brute(0, 0) << endl;

	// top-down
	cout << Topdown(0) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

파도반 수열에는 일정한 규칙이 있는데, 이를 점화식으로 표현하면 다음과 같다.

padovan(N) = padovan(N-2) + padovan(N-3)

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

#include <iostream>
using namespace std;

long long memo[101];

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

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

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

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

	for (int i = 4; i <= N; i++)
		memo[i] = memo[i - 2] + memo[i - 3];
	
	return memo[N];
}

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

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

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

	return 0;
}

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

[문제 링크]

1x2, 2x1 타일을 사용해서 2 x n 직사각형을 채우는 문제의 업그레이드 버젼이다.

먼저, 1x2, 2x1 타일을 사용하는 타일링 문제의 점화식이 dp(n) = dp(n-1) + dp(n-2) 라는 것을 기억하자.

위 점화식에서 dp(n-1)은 2x(n-1) 타일을 채우는 방법의 수 * 2x1 타일을 채우는 방법의 수를 나타내는데,

2 x 1 타일을 채우는 방법이 한가지밖에 존재하지 않기 때문에 *1 이 생략된 것이다.

dp(n-2) 도 마찬가지로 2x(n-2) 타일을 채우는 방법의 수 * 2x2 타일을 채우는 방법의 수를 나타내는데,

2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법과 2x1 타일 2개로 채우는 방법이 존재하지만

2x1 타일 2개로 채우는 방법은 dp(n-1)과 중복되므로 제외시킨다.

따라서 2x2 타일을 채우는 방법도 한가지 밖에 존재하지 않기 때문에 *1이 생략된 것이다.

이 문제는 1x2, 2x1 타일과 추가로 2x2 타일을 사용할 수 있다고 한다.

2x2 타일이 추가되었기 때문에 2x1 타일을 채우는 방법의 수는 변함이 없다.

하지만 2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법에 추가로 2x2 타일 1개로 채우는 방법이 생기게 되므로 총 두가지 방법이 존재하게 되어 * 2를 해주어야 한다.

따라서 이 문제의 점화식은 다음과 같다.

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

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

#include <iostream>
using namespace std;

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

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

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

	return ret = (Topdown(n - 1) + (Topdown(n - 2) * 2)) % MOD;
}

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

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

	return memo[n];
}

int main(void)
{
	int n;
	cin >> n;
	
	// Top-down
	cout << "Top-down: " << Topdown(n) << endl;
	
	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(n) << endl;

	return 0;
}

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