급하게임개발

https://www.acmicpc.net/problem/7453

이 문제의 경우 처음에 투포인터로 분류가 되어있어 풀려고 했는데 투포인터가 불가능 하게 리스트가 4개 있어서 안될거 같다는 생각을 했다 그래서 투포인터를 사용하기 위해서는 어떻게 해야할까라고 생각해봤을 때 a와 b의 합을 c와 d의 합의 모든 경우의 수로 리스트를 만들려고 하였다

즉 c와 d의 합을

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

이런 식으로 만들어 주고

a와 b의 합의 -  를 붙인거가 c와 d를 합친 cmp에 있는 갯수를 더해서 경우의 수를 구하면 된다 근데 갯수를 어떻게 구할지를 생각해보면 -(a+b) 에 대한 거를 algorithm 헤더에 있는 lower_bound와 upper_bound를  이분 탐색으로 해당 수를 찾아 낮은 인덱스 와 높은 인덱스를 찾아 차이가 해당 수의 갯수이니 이를 더해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[4];
vector<int> cmp;
long long ans = 0;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < 4; i++) {
		v[i].resize(n + 1);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> v[j][i];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cmp.push_back(v[2][i] + v[3][j]);
		}
	}

	sort(cmp.begin(), cmp.end());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp = v[0][i] + v[1][j];
			int lowIdx = lower_bound(cmp.begin(), cmp.end(), -tmp)- cmp.begin();
			int upIdx = upper_bound(cmp.begin(), cmp.end(), -tmp) - cmp.begin();
			ans += (upIdx - lowIdx);
		}
	}
	cout << ans;
}

https://www.acmicpc.net/problem/9252

이 문제는 전형 적인 dp 문제 였다 

어느 문자를 다른 문자의 n번째 문자의 이전 문자까지의 가장 긴 LCS를 구하는 문제이다

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

int arr[1001][1001]; // 배열 크기 수정
string s1, s2;
vector<char> lcsV; // LCS 결과 문자열 저장

void lcsF() {
    int sizeOfs1 = s1.size();
    int sizeOfs2 = s2.size();

    // DP 배열 채우기
    for (int i = 1; i <= sizeOfs1; i++) {
        for (int j = 1; j <= sizeOfs2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }
            else {
                arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
            }
        }
    }

    // 역추적하여 LCS 문자열 구성
    int i = sizeOfs1, j = sizeOfs2;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcsV.push_back(s1[i - 1]);
            i--;
            j--;
        }
        else if (arr[i - 1][j] > arr[i][j - 1]) {
            i--;
        }
        else {
            j--;
        }
    }
    reverse(lcsV.begin(), lcsV.end()); // LCS 문자열을 올바른 순서로 변경
}

int main() {
    cin >> s1 >> s2;

    lcsF();

    // LCS 길이 출력
    cout << arr[s1.size()][s2.size()] << endl;

    // LCS 문자열 출력
    for (char c : lcsV) {
        cout << c;
    }
    cout << endl;

    return 0;
}

https://www.acmicpc.net/problem/6497

이 문제는 그냥 크루스칼 알고리즘인데 출력이 불친절하다 그냥 00전에 테스트케이스가 여러개 나오는 문제였다

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

int parent[200000];
int n, m;
vector<pair<int, pair<int, int>>> inputData;

int findParent(int x) {
    if (parent[x] == x)
        return x;
    else
        return parent[x] = findParent(parent[x]);
}

bool isSameParent(int x, int y) {
    return findParent(x) == findParent(y);
}

void uni(int x, int y) {
    x = findParent(x);
    y = findParent(y);
    parent[y] = x;
}

int main() {
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break; // 종료 조건

        inputData.clear();
        int tmp1, tmp2, tmp3;
        int cost = 0, totalCost = 0;

        for (int i = 0; i < m; i++) {
            cin >> tmp1 >> tmp2 >> tmp3;
            inputData.push_back({ tmp3, {tmp1, tmp2} });
            totalCost += tmp3;
        }

        // 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        sort(inputData.begin(), inputData.end()); // 간선 정렬

        for (int i = 0; i < inputData.size(); i++) {
            if (!isSameParent(inputData[i].second.first, inputData[i].second.second)) {
                uni(inputData[i].second.first, inputData[i].second.second);
                cost += inputData[i].first;
            }
        }

        cout << totalCost - cost << "\n";
    }

    return 0;
}

https://www.acmicpc.net/problem/17404

이 문제는 RGB거리 문제의 발전형이다 기존에는 사이클을 검사안했으나 이번에는 사이클을 검사해야한다 그래서 이문제를 풀기위한 핵심은
첫번째 집의 색깔을 정해주고 나머지 집들의 dp를 돌리는 것이다

어떻게 정하면 되는지는 우리는 원래 dp 를 풀때 각라인의 최솟값을 넣는데 이 최솟값을 만들 때 우리는 나머지 선택을 하지못하게 하면된다

해당 예제를 예시로 보자

평소에 우리가 dp를 구할  때 우리는 26 40 83을 min 때리고 이를 바탕으로 다음라인에서 비교 해준다 평소대로 하게된다면 우리는 다음  dp 행을 구할 때 최소 색깔을 선택함으로 우리가 색을 정할 수가 없다 만약에 우리가 999999 40 999999 이런식으로 dp 행을 놓게 된다면 무조건적으로 40이 선택된다 이러한 로직을 바탕으로

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

해당 로직이 작성된다 first는 첫번째 집이 고른 색이다 첫번째 집이 빨간색을 골랐을 때 우리는 파란색 초록색을 고르는 선택지를 없애버리기 위해서 dp행이 첫번째의 고를 선택지 에서 지워버리는 것이다



이로직 뺴고는 dp 점화식 자체는 별반 다른지 않다

내가 빨간색을 선택했을 때 이전에 초록색 혹은 파란색을 선택했을 때 의 값중 최솟 값을 선택하면된다 

즉 점화식 자체는

	for (int i = 1; i < n; i++) {
		dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
	}

이렇게 된다

전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][3];
int dp[1001][3];
int maxVal = 987654321;
int answer = 987654321;
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}

	for (int first = 0; first < 3; first++) {
		for (int i = 0; i < 3; i++) {
			if (first == i) {
				dp[0][i] = arr[0][i];
			}
			else {
				dp[0][i] = maxVal;
			}
		}

		for (int i = 1; i < n; i++) {
			dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
		}

		for (int i = 0; i < 3; i++) {
			if (first == i)
				continue;
			answer = min(answer, dp[n-1][i]);
		}
	}

	cout << answer;
}

https://www.acmicpc.net/problem/2473

이 문제는 3개를 어떻게 할까 고민하다가 그냥 1개를 정해놓고 0의 가장 가까운 투포인터를 하면 되겠다는 생각을 했다 즉 하나의수는 고정인 상태에서 0보다크면 혹은 작으면 에 대해서 m값과 r값을 바꿔주면서 최솟값을 저장하는 방식으로 진행했다

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
int n;
vector<long long> inputData;
long long result = 3000000001;
long long ans[3];
int main() {
	cin >> n;

	long long tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());
	int l, m, r;
	for (int l = 0; l < n - 2; l++) {
		m = l + 1;
		r = n - 1;
		while (m < r) {
			long long val = inputData[l] + inputData[m] + inputData[r];
			if (abs(val) < result) {
				result = abs(val);

				ans[0] = inputData[l];
				ans[1] = inputData[m];
				ans[2] = inputData[r];
			}
			if (val < 0) {
				m++;
			}
			else {
				r--;
			}
		}
	}

	for (int i = 0; i < 3; i++) {
		cout << ans[i] << " ";
	}
}

https://www.acmicpc.net/problem/13460

이 문제는 겁나 복잡해보였지만 막상 풀고나니 이해하기 쉬웠다

그냥 두가지 케이스 빨간공 파란공 각각 움직인다음 겹칠때 혹은 구멍에 들어갈때의 조건식만 추가해주면 되었다

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int arr[10][10];
struct INFO {
	int Rx, Ry, Bx, By, count;
};
int n, m;
INFO start;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[11][11][11][11] = { 0, };
int bfs() {
	queue<INFO> bfsQ;
	bfsQ.push(start);

	int ans = -1;
	visited[start.Rx][start.Ry][start.Bx][start.By] = 1;
	while (!bfsQ.empty()) {
		INFO cur = bfsQ.front();
		bfsQ.pop();
		if (cur.count > 10)break;

		if (arr[cur.Rx][cur.Ry] == 4 && arr[cur.Bx][cur.By] != 4) {
			ans = cur.count;
			break;
		}

		for(int i=0; i<4; i++){
			int nextRy = cur.Ry;
			int nextRx = cur.Rx;
			int nextBy = cur.By;
			int nextBx = cur.Bx;
			while (1) {
				if (arr[nextRx][nextRy] != 1 and arr[nextRx][nextRy] != 4) {
					nextRx += dx[i];
					nextRy += dy[i];
				}
				else {
					if (arr[nextRx][nextRy] == 1) {
						nextRx -= dx[i]; 
						nextRy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//blue 구슬 벽이나 구멍일때까지 한 방향으로 이동함
			while (1) {
				if (arr[nextBx][nextBy] != 1 and arr[nextBx][nextBy] != 4) {
					nextBx += dx[i];
					nextBy += dy[i];
				}
				else {
					if (arr[nextBx][nextBy] == 1) {
						nextBx -= dx[i]; 
						nextBy -= dy[i]; //벽일 경우 이전위치로
					}
					break;
				}
			}

			//red와 blue가 겹칠 경우
			if (nextRx == nextBx and nextRy == nextBy) {
				if (arr[nextRx][nextRy] != 4) {
					int red_dist = abs(nextRx - cur.Rx) + abs(nextRy - cur.Ry);
					int blue_dist = abs(nextBx - cur.Bx) + abs(nextBy - cur.By);

					if (blue_dist > red_dist) {
						nextBx -= dx[i];
						nextBy -= dy[i];
					}
					else {
						nextRx -= dx[i];
						nextRy -= dy[i];
					}
				}
			}

			//방문여부 확인
			if (visited[nextRx][nextRy][nextBx][nextBy] == 0) {
				visited[nextRx][nextRy][nextBx][nextBy] = 1;
				INFO next;
				next.Rx = nextRx;
				next.Ry = nextRy;
				next.Bx = nextBx;
				next.By = nextBy;
				next.count = cur.count + 1;

				bfsQ.push(next);

			}
		}

	}
	return ans;
}

int main() {
	cin >> n >> m;
	string input;

	for (int i = 0; i < n; i++) {
		cin >> input;
		for (int j = 0; j < m; j++) {
			if (input[j] == '#') {
				arr[i][j] = 1;
			}
			else if (input[j] == 'R') {
				arr[i][j] = 2;
				start.Rx = i;
				start.Ry = j;
			}
			else if (input[j] == 'B') {
				arr[i][j] = 3;
				start.Bx = i;
				start.By = j;
			}
			else if (input[j] == 'O') {
				arr[i][j] = 4;
			}
		}
	}
	start.count = 0;
	cout << bfs();
}

https://www.acmicpc.net/problem/1253

이 문제는 이분탐색 문제이다 처음 그냥 대충  쉽게 접근하다가 틀렸는데 같은수가 여러번 들어갈수 있음을 망각했다

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long  n;
vector<long long > inputData;
int main() {
	cin >> n;
	long long  tmp;
	long long  cnt = 0;

	for (long long i = 0; i < n; i++) {
		cin >> tmp;
		inputData.push_back(tmp);
	}
	sort(inputData.begin(), inputData.end());

	for (long long i = 0; i < n; i++) {
		long long left = n-1;
		long long right = 0;
		
		while (right <n && left>=0  && right<left) {
			if (right == i) {
				if (right < n-1) {
					right += 1;
				}
			}
			if (left == i) {
				if (left > 0) {
					left -= 1;
				}
			}
			if (left == right) {
				break;
			}
			if ((inputData[right] + inputData[left]) == inputData[i]) {
				cnt += 1;
				break;
			}
			else if ((inputData[right] + inputData[left]) > inputData[i]) {
				left -= 1;
			}
			else if ((inputData[right] + inputData[left]) < inputData[i]) {
				right += 1;
			}
		}
	}
	cout << cnt;
}

전체 코드는 이렇게 된다 처음에는 2/n 기준으로 양옆으로 펼쳐지면서 값을 찾으려 했으나 이렇게 하면 못찾을 때 가 발생해서 양옆에서 조이는 방식으로 진행 했다

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

이 문제는 그냥 여러개 섞어놓은 문제이다 병사를 배정하는것은 조합으로 dfs로 풀면 되고 
병사들이 몬스터를 잡는건 bfs로 풀면된다 조합에대한 모든것을 bfs함으로 브루트포스이기도 하다 사실이문제는 단지 기본적인 알고리즘 여러개를 섞어놓은것이다
주의할 점은 bfs를 할때

int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};

이 순서대로 해야한다 bfs가 거리가 가까운거는 보장하지만 왼쪽 탐색을 하기위해서는 해당 인덱스를 따라 해야지 왼쪽부터 탐색한다
또한 탐색하자마자 바로 0으로 바꾸지말고 중복으로 한 몬스터를 때릴수 있으므로 4로 체크하고 이후에 0으로 바꾼다

#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int originArr[16][15];
int copyArr[16][15];
int N, M, D;
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};
int maxNum;
bool isVisited[16][15] = { 0, };
bool AllDie() {
	bool isDie = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copyArr[i][j] == 1)
				isDie = false;
		}
	}
	return isDie;
}
void CopyOrigin() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = originArr[i][j];
		}
	}
}
bool CanGo(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M ) {
		return true;
	}
	else {
		return false;
	}
}
void downEnemy() {
	for (int i = N-1 ; i > 0; i--) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = copyArr[i - 1][j];
			if (copyArr[i][j] == 4)
				copyArr[i][j] = 0;
		}
	}
	for (int i = 0; i < M; i++) {
		copyArr[0][i] = 0;
	}
}
int bfs(int armyX, int armyY) {
	queue<pair<int, pair<int, int>>> ArmyQ;
	ArmyQ.push({ 0,{armyX,armyY} });
	int count = 0;
	while (!ArmyQ.empty()) {
		int curX = ArmyQ.front().second.first;
		int curY = ArmyQ.front().second.second;
		int cost = ArmyQ.front().first;
		ArmyQ.pop();
		if (cost > D)
			break;
		if (copyArr[curX][curY] == 4) {
			break;
		}
		if (copyArr[curX][curY] == 1) {
			copyArr[curX][curY] = 4;
			count += 1;
			break;
		}

		for (int i = 0; i < 3; i++) {
			int nextX = curX + goX[i];
			int nextY = curY + goY[i];
			if (CanGo(nextX, nextY)) {
				ArmyQ.push({ cost + 1,{nextX,nextY} });
			}
		}
	}
	return count;
}
void dfs(int start, int count) {
	if (count == 3) {// 병사를 3명 다배치 했을 경우
		CopyOrigin();
		int num = 0;
		while (!AllDie()) {
			for (int i = 0; i < M; i++) {
				if (copyArr[N][i] == 3) {
					num += bfs(N, i);
				}
			}
			downEnemy();
		}
		maxNum = max(num, maxNum);
	}
	
	else {
		for (int i = start+1; i < M; i++) {
			originArr[N][i] = 3;
			dfs(i, count + 1);
			originArr[N][i] = 2;
		}
	}
}
int main() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> originArr[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 2;
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 3;
		dfs(i, 1);
		originArr[N][i] = 2;
	}
	cout << maxNum;
}