Codetesing의 코딩공부

비트마스크를 활용한 DP문제다.

아까 풀어봤기 때문에 어려움없이 쉽게 풀 수 있었다.

다만 여기선 무조건 있어야 되기 때문에 and 연산자를 사용했다.

#define MOD 1000000007

#include<iostream>
#include<string>
#include<cstring>

using namespace std;

long long DP[10001][16];

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		string in; cin >> in;
		int len = in.length();
		memset(DP, 0, sizeof(DP));

		for (int i = 0; i < len; i++)
		{
			int admin = 1 << (in[i] - 'A');

			for (int j = 1; j < 16; j++)
			{
				if (i == 0)
				{
					if ((j & admin) != 0 && (j & 1) != 0)
					{
						DP[i][j] = 1;
					}
				}
				else
					if (DP[i - 1][j] != 0)
						for (int k = 1; k < 16; k++)
							if ((k & j) != 0 && (k & admin) != 0)
							{
								DP[i][k] += DP[i - 1][j];
								DP[i][k] %= MOD;
							}
			}
		}

		long long out = 0;
		for (int i = 1; i < 16; i++)
		{
			out += DP[len - 1][i];
			out %= MOD;
		}

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

비트마스크를 사용하여 DP를 활용한 문제이다.

비트마스크 관련 문제는 처음 풀어보았기 때문에 비트마스크에 대해 공부하고 풀었다.

동적프로그래밍/비트마스크/계단수 : 백준 10844번, 1562번 (tistory.com)​

비트마스크는 2진법을 활용해 부분집합을 표현하는 방식인것 같다.

 i는 자릿수며 초기설정 i == 1 일때 모두 삐끗수이기 때문에 1로 설정한다.

다음 숫자에서 0 - 9까지 들어갈 수 있는지 확인 하기위해 j = 0 - 9, k = 0 - 1023 반복하는데 (1 << j) | k를 사용해 상태를 확인한다.

이 문제에서는 0 - 9까지이고 0 - 9까지 모두 사용해야 하기 때문에, DP[n][][1023]의 합을 답으로 한다.

#define MOD 1000000000

#include<iostream>

using namespace std;

int DP[101][10][1 << 10];

void BIT_MASK()
{
	for (int i = 1; i < 10; i++)
		DP[1][i][1 << i] = 1;

	for(int i = 0; i < 100; i++)
		for(int j = 0; j < 10; j++)
			for (int k = 0; k < 1024; k++)
			{
				if(j != 0)
					DP[i + 1][j][(1 << j) | k] = (DP[i + 1][j][(1 << j) | k] + DP[i][j - 1][k]) % MOD;
				if(j != 9)
					DP[i + 1][j][(1 << j) | k] = (DP[i + 1][j][(1 << j) | k] + DP[i][j + 1][k]) % MOD;
			}
}

int STAIR_NUM(int n)
{
	int sum = 0;

	for (int i = 0; i < 10; i++)
	{
		sum += DP[n][i][1023];
		sum %= MOD;
	}

	return sum;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	BIT_MASK();

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N; cin >> N;
		int out;

		if (N < 10)
			out = 0;
		else
			out = STAIR_NUM(N);

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

쉬운 DP문제이다. 자주 풀었던 문제이기 때문에 어려움은 없었다.

연속된 정수의 합을 구하는 문제이기 때문에, 앞에 값을 쓸지 안쓸지만 구분하면 된다. 

쓴다면 (앞에 값 + 현재 값 > 현재 값) 더한값을 저장, 안쓴다면 (앞에 값 + 현재 값 < 현재 값) 현재값을 저장.

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

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int N; cin >> N;
		vector<int> in(N);
		vector<int> DP(N, 0);

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

		DP[0] = in[0];

		for (int i = 1; i < N; i++)
			DP[i] = max(DP[i - 1] + in[i], in[i]);

		int out = *max_element(DP.begin(), DP.end());

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}

골드4 문제이며 DP와 DFS를 사용하는 문제.

주의할 점은 DP를 0이 아닌 -1로 초기화 해줘서 길이 없는건지 확인하지 않은건지 차이를 줘야함.

문제 링크 : 1520번: 내리막 길 (acmicpc.net)

#include <iostream>
#include <vector>

using namespace std;

int ROTATE_X[] = { -1, 1, 0, 0 };
int ROTATE_Y[] = { 0, 0, -1, 1 };

int DP[501][501];
int map[501][501];
int N, M;

int DFS(int row, int col)
{
	if (row == N && col == M)
		return 1;
	if (DP[row][col] != -1)
		return DP[row][col];

	DP[row][col] = 0;

	int next_row, next_col;
	for (int i = 0; i < 4; i++)
	{
		next_row = row + ROTATE_X[i];
		next_col = col + ROTATE_Y[i];

		if (next_row >= 1 && next_row <= N && next_col >= 1 && next_col <= M)
			if (map[next_row][next_col] < map[row][col])
				DP[row][col] += DFS(next_row, next_col);
	}

	return DP[row][col];
}

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

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			DP[i][j] = -1;
		}

	cout << DFS(1, 1) << '\n';

	return 0;
}