굳건하게

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

[ 알고리즘풀이 ]

 2차원 DP 배열을 이용해서 문제를 해결할 수 있습니다. 입력되는 첫 번째 문자배열을 A, 두 번째 문자배열을 B라고 하겠습니다.

 DP[X][Y] : A의 0 ~ X번 째, B의 0 ~ Y번 째까지 중 가장 긴 부분 공통 문자배열.

 DP[i][j] 

 -A[i]와 B[j] 같다면, DP[i - 1][j - 1]에다가 A[i] 를 더한 문자배열.

 -A[i]와 B[j]가 다르다면, DP[i][j] 는 DP[i - 1][j] 와 DP[i][j - 1] 중 더 긴 문자배열.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

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

	string A, B, dp[40][40] = {};
	cin >> A >> B;
	bool check = false;
    //초기값
	for (int i = 0; i < A.length(); i++)
		if (A[i] == B[0] || check){
			dp[i][0] = B[0];
			check = true;
		}
	check = false;
    //초기값
	for (int j = 0; j < B.length(); j++)
		if (A[0] == B[j] || check){
			dp[0][j] = A[0];
			check = true;
		}
	//DP배열
	for (int i = 1; i < A.length(); i++) {
		for (int j = 1; j < B.length(); j++) {
			if (A[i] == B[j]) {
				dp[i][j] = dp[i - 1][j - 1] + A[i];
			}
			else {
				if (dp[i - 1][j].length() < dp[i][j - 1].length())
					dp[i][j] = dp[i][j - 1];
				else
					dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[A.length() - 1][B.length() - 1];
	return 0;
}

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

[ 알고리즘풀이 ]

 Binary Search 를 이용하면 O(NlogN + MlogN) 복잡도로 문제를 해결할 수 있습니다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

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

	int N, M;
	cin >> N >> M;
	string A, B;
	vector<pair<string, string>> v;
	for (int i = 0; i < N; i++) {
		cin >> A >> B;
		v.push_back(make_pair(A, B));
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < M; i++) {
		cin >> A;
		int left = 0, right = N - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (v[mid].first == A){
				cout << v[mid].second << '\n';
				break;
			}
			else if (v[mid].first < A) {
				left = mid + 1;
			}
			else
				right = mid - 1;
		}
	}
	return 0;
}

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

[ 알고리즘풀이 ]

 구현 문제로 모든 경우에 대해서 해당 게임을 구현함으로써, 최대로 죽일 수 있는 적의 수를 찾으면 됩니다.

1. 궁수배치

 3중 for문을 이용해 궁수를 배치하는 모든 경우마다 게임 함수를 호출.

2. 배치된 궁수들로 게임 진행

 게임 함수는 먼저 map을 복사해 tempMap을 만든 후, tempMap에서 전달받은 궁수 배치 상태로 게임을 진행합니다. 게임은 ( 적 공격 - 적 이동 ) 을 하나의 Round로 보면 총 N번의 Round를 진행하게 됩니다.

3. 적 공격

 적 공격은 현재 궁수 위치에서 거리가 D 이하인 적들 중 거리가 가장 가깝고! 가장 왼쪽( 열의 값이 작은 ) 적을 공격하게 되고, 같은 적을 다른 궁수가 공격할 수 있으므로 각 궁수마다 공격하게 되는 적은 bool attacked[][] 배열을 이용해서 check 해야 합니다. 적이 있는 모든 위치(x, y)를 순회하며 거리가 D보다 작다면 vector 배열에 (D, y, x) 순으로 push를 해줍니다. 이때, sort 함수를 이용할 것이므로 우선 순위가 가장 큰 거리, 그 다음인 열, 그 다음인 행 순으로 push를 해야합니다. 그 후, 현재 궁수에서 공격가능한 적들을 담은 vector 배열을 sorting 해 가장 우선시 되는 적을 공격합니다.

4. 적 이동

 적 이동은 그냥 현재 게임 상태인 tempMap을 한 칸씩 아래로 shift 하고, 맨 윗줄에는 0을 채워주면 됩니다.

5. 과정 반복

 다시 3번과 4번을 반복하고, 게임이 끝났다면 다시 1번부터 새로운 궁수를 배치해 게임을 진행합니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int N, M, D, map[15][15] = {}, tempMap[15][15] = {}, ans = -1;

int getDistance(int x, int y, int A) {
	return abs(N - x) + abs(A - y);
}

int attack(int list[3]) {
	bool attacked[15][15] = {};
	for (int k = 0; k < 3; k++) {
		vector < pair<int, pair<int, int>>> v;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (tempMap[i][j] == 1) { //적이있어.
					int d = getDistance(i, j, list[k]); //현재궁수와 적사이의거리
					if (d <= D)
						v.push_back(make_pair(d, make_pair(j, i)));
				}
			}
		}
		sort(v.begin(), v.end());
		if (!v.empty())
			attacked[v[0].second.second][v[0].second.first] = true;
	}
	int count = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (attacked[i][j]) {
				count++;
				tempMap[i][j] = 0;
			}
	return count;
}

void move(void) {
	for (int i = N - 1; i > 0; i--)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = tempMap[i - 1][j];
	for (int j = 0; j < M; j++)
		tempMap[0][j] = 0;
	return;
}

void gameStart(int list[3]) {
	// 궁수를 A, B, C 위치에 배치 && map 복사
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = map[i][j];

	int attackCount = 0;
	// 한 줄씩 진행.
	for (int i = 0; i < N; i++) {
		//공격
		attackCount += attack(list);
		//이동
		move();
	}
	ans = max(ans, attackCount);
	return;
}

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

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

	for (int i = 0; i < M; i++)
		for (int j = i + 1; j < M; j++)
			for (int k = j + 1; k < M; k++) {
				int list[3] = { i, j, k };
				gameStart(list);
			}

	cout << ans;
	return 0;
}

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

[ 알고리즘풀이 ]

파이프 옮기기 1과 동일하나 long long 배열로 선언해줘야한다.

( 파이프 옮기기 1 풀이 : https://travelbeeee.tistory.com/277 )

#include<iostream>

int N, map[33][33] = {};
long long dp[3][33][33] = {};

using namespace std;

bool check(int x, int y) {
	if (1 <= x && x <= N && 1 <= y && y <= N && map[x][y] == 0)
		return true;
	return false;
}

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

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	dp[0][1][2] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) {
			if (check(i, j - 1) && check(i, j))
				dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];
			if (check(i - 1, j) && check(i, j))
				dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
			if (check(i - 1, j - 1) && check(i - 1, j) && check(i, j - 1) && check(i, j))
				dp[2][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
		}
	}

	cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

	return 0;
}