굳건하게

문제 : https://www.acmicpc.net/problem/15990

[ 알고리즘풀이 ]

DP[0][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 1로 끝나는 경우.

DP[1][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 2로 끝나는 경우.

DP[2][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 3로 끝나는 경우.

→ DP[0][N] = DP[1][N - 1] + DP[2][N - 1];

→ DP[1][N] = DP[0][N - 2] + DP[2][N - 2];

→ DP[2][N] = DP[0][N - 3] + DP[1][N - 3];

#include<iostream>
#define M 1000000009

using namespace std;

int T, N, dp[3][100001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dp[0][1] = 1, dp[1][2] = 1, dp[0][3] = 1, dp[1][3] = 1, dp[2][3] = 1;
	for (int i = 4; i <= 100000; i++) {
		dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % M;
		dp[1][i] = (dp[0][i - 2] +  dp[2][i - 2]) % M;
		dp[2][i] = (dp[0][i - 3] + dp[1][i - 3]) % M;
	}
	cin >> T;
	while (T--) {
		cin >> N;
		cout << ((dp[0][N] + dp[1][N])% M + dp[2][N])% M << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/15989

[ 알고리즘풀이 ]

DP[0][N] : N을 1을 무조건 한 번 이상 사용하면서 만드는 경우의 수.

DP[1][N] : N을 1을 사용 안하고, 2를 무조건 한 번 이상 사용하면서 만드는 경우의 수.

DP[2][N] : N을 1, 2를 사용 안하고 3을 무조건 한 번 이상 사용하면서 만드는 경우의 수.

→ DP[0][N] = DP[0][N - 1] + DP[1][N - 1]+ DP[2][N - 1];

→ DP[1][N] = DP[1][N - 2] + DP[2][N - 2];

→ DP[2][N] = DP[2][N - 3];

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T, N, dp[3][10001] = {};
	dp[0][1] = 1, dp[0][2] = 1, dp[1][2] = 1, dp[0][3] = 2, dp[2][3] = 1;
	for (int i = 4; i <= 10000; i++) {
		dp[0][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]);
		dp[1][i] = (dp[1][i - 2] + dp[2][i - 2]);
		dp[2][i] = dp[2][i - 3];
	}
	cin >> T;
	while (T--) {
		cin >> N;
		cout << dp[0][N] + dp[1][N] + dp[2][N] << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/12100

[ 알고리즘풀이 ]

1. 백트레킹을 이용해서 4개의 방향에 대해서 총 5번 어떤 방향으로 블록을 합칠지 경우의 수를 구한다.

2. 블록을 합치는 함수를 구현한다. 이때, 블록을 합치는 방향은 위로 통일한다.

- 1) 빈 공간이 있으면 빈 공간을 다 shift 한다.

- 2) 같은 값이 있으면 블록을 합쳐준다.

- 3) 블록을 합치는 과정에서 생긴 빈 공간을 다시 shift 한다.

3. 블록을 위로만 합칠 것이므로, 1번에서 구한 방향에 맞춰 Map을 회전한 후 블록을 합친다.

4. 5번 블록을 합쳤으면, 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, map[20][20] = {}, ans = -1;

void getScore(int tempMap[20][20]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			ans = max(ans, tempMap[i][j]);
	return;
}

void move(int tempMap[20][20]) {
	// 공백을 없애자.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (tempMap[i][j] == 0) {
				int k = i, jump = 0;
				while (k < N && tempMap[k][j] == 0) {
					jump++;
					k++;
				}
				for (int k = i; k + jump < N; k++)
					tempMap[k][j] = tempMap[k + jump][j];
				for (int k = N - 1; k >= N - jump; k--)
					tempMap[k][j] = 0;
			}
		}
	}
	// 합치자.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N - 1; i++) {
			if (tempMap[i][j] == tempMap[i + 1][j]) {
				tempMap[i][j] *= 2;
				tempMap[i + 1][j] = 0;
			}
		}
	}
	// 다시 공백 없애기.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (tempMap[i][j] == 0) {
				int k = i, jump = 0;
				while (k < N && tempMap[k][j] == 0) {
					jump++;
					k++;
				}
				for (int k = i; k + jump < N; k++)
					tempMap[k][j] = tempMap[k + jump][j];
				for (int k = N - 1; k >= N - jump; k--)
					tempMap[k][j] = 0;
			}
		}
	}
}

void changeMap(int tempMap[20][20], int dir) {
	int dumpMap[20][20] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dumpMap[i][j] = tempMap[i][j];

	if (dir == 0) { //왼쪽
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - j][i];
	}
	else if (dir == 1) { //아래쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - i][j];

	}
	else if (dir == 2) { //오른쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}

	move(tempMap);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dumpMap[i][j] = tempMap[i][j];

	if (dir == 0) { //왼쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}
	else if (dir == 1) { //아래쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - i][j];
	}
	else if (dir == 2) { //오른쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}

	return;
}
void playGame(vector<int> v) {
	int tempMap[20][20] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tempMap[i][j] = map[i][j];
	for (int i = 0; i < 5; i++) {
		changeMap(tempMap, v[i]);
	}
	getScore(tempMap);
	return;
}

void BT(vector<int> v) {
	if (v.size() == 5) {
		playGame(v);
		return;
	}
	for (int i = 0; i < 4; i++) {
		v.push_back(i);
		BT(v);
		v.pop_back();
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	vector<int> v;
	BT(v);

	cout << ans;

	return 0;
}

다음 번에는 코드를 개선해보자,,,,!!

문제 : https://www.acmicpc.net/problem/15993

[ 알고리즘풀이 ]

DP[0][X] = X를 1, 2, 3의 합으로 나타내는 방법 중 사용한 수의 개수가 짝수인 방법의 수

DP[1][X] = X를 1, 2, 3의 합으로 나타내는 방법 중 사용한 수의 개수가 홀수인 방법의 수

→ DP[0][X] = DP[1][X - 1] + DP[1][X - 2] + DP[1][X - 3];

→ DP[1][X] = DP[0][X - 1] + DP[0][X - 2] + DP[0][X - 3];

#include<iostream>
#define M 1000000009

using namespace std;

int N, K, dp[2][1000001] = { };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dp[1][1] = 1, dp[0][2] = 1, dp[1][2] = 1, dp[0][3] = 2, dp[1][3] = 2;
	for (int i = 4; i <= 1000000; i++) {
		dp[0][i] = ((dp[1][i - 1] + dp[1][i - 2]) % M + dp[1][i - 3]) % M;
		dp[1][i] = ((dp[0][i - 1] + dp[0][i - 2]) % M + dp[0][i - 3]) % M;
	}

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		cout << dp[1][n] << ' ' <<  dp[0][n] << '\n';
	}
	return 0;
}