급하게임개발

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/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/17396

이 문제는 다 풀어놓고 하나를 실수 해서 조금 헤맸었다
이 문제는 일반적인 다익스트라 문제이다 이에 소스코드는 이렇게 되고 25% 에서 이슈가 있었다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[100000];
vector<int> distance_v;
int testCase;
int n, d, c;
#define INF 1000000001
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,startNode });
	while (!djikstra_pq.empty())
	{
		int vertex = djikstra_pq.top().second;
		int toCost = djikstra_pq.top().first;
		djikstra_pq.pop();
		if (toCost > distance_v[vertex])
			continue;

		for (int i = 0; i < edgeList[vertex].size(); i++) {
			int nextVertex = edgeList[vertex][i].first;
			int nextCost = edgeList[vertex][i].second;
			if (distance_v[nextVertex] > nextCost + toCost) {
				distance_v[nextVertex] = nextCost + toCost;
				djikstra_pq.push({ nextCost + toCost,nextVertex });
			}
		}
	}
}
int main() {
	cin >> testCase;
	for (int i = 0; i < testCase; i++) {
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			int from, to, cost;
			cin >> from >> to >> cost;
			edgeList[to].push_back({ from,cost });
		}
		distance_v.assign(n + 1, INF);
		int cpuCnt, lastSecond;
		djikstraSolution(c);
		lastSecond = 0;
		cpuCnt = 0;
		distance_v[c] = 0;
		for (int i = 1; i <= n; i++) {
			if (distance_v[i] != INF) {
				cpuCnt++;
				if (distance_v[i] > lastSecond) {
					lastSecond = distance_v[i];
				}
			}
			edgeList[i].clear();
		}
		cout << cpuCnt << " " << lastSecond << endl;
	}
}

이런식으로 되는데 내가 처음에 distanceVector를 초기화 해줄 때 나에서부터 나까지의  거리는 0이라고 설정을 안해놓았었다 그 후 무조건 감염 PC는 하나니 cpuCnt값을 1로두고 셌다 근데 문제는 여기서 a->b b->a 로가는 경로가 생길시 a의 경로값이 갱신 되면서 

			if (distance_v[i] != INF) {
				cpuCnt++;

이 부분에서 CPUCNT가 하나더 증가해서 이미센 감염피씨를 한번 더세면서 문제가 틀렸었다 이에 감염된 피씨의 초를 0으로 바꿔주고 cpuCNt의 값을 0으로 바꿔주니 정상적으로 나왔다

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=cpp

이 문제는 프로그래머스 알고리즘 고득점 Kit의 문제이다 
Programmers LV3 문제 치고는 접근 법이 매우 쉬웠다 이 문제의 경우

이렇게 생긴 벡터가 제공이 된다 

실제 자료형은 이렇게 제공이 되는데
이 문제는 똑같은 삼각형을 만들고 나의 이전 행에 있는 나를 기준으로 양대각선의 있는 값중 나와의 합이 최대가 되는 애와의 합을 내가 현재 있는 위치에 넣는 것이다

즉 이그림을 보면 3번 째줄에 와서 보면 1을 기준으로 내가 선택할 수 있는 것은 이전행의 10과 15이다 이중 두값중 1과 합했을때 큰값을 16임으로 나의 위치에 16을 넣어준다 이를 계속 반복 해주면 된다

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

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> dpV;
    vector<int> rowV1;
    dpV.push_back(rowV1);
    dpV[0].push_back(triangle[0][0]);
    for(int i=1; i<triangle.size(); i++){
        vector<int> rowV;
        dpV.push_back(rowV);
        
        for(int j=0; j<triangle[i].size(); j++){
            if(j==0){
                dpV[i].push_back(dpV[i-1][j]+triangle[i][j]);
            }
            else if(j==triangle[i].size()-1){
                dpV[i].push_back(dpV[i-1][j-1]+triangle[i][j]);
            }
            else{
                dpV[i].push_back(max(triangle[i][j]+dpV[i-1][j-1],triangle[i][j]+dpV[i-1][j]));
            }
        }
    }
    int answer = 0;
    for(int i=0; i<dpV[triangle.size()-1].size(); i++){
        answer=max(answer,dpV[triangle.size()-1][i]);
    }
    return answer;
}

위에 코드를 보게 되면 똑같은 이차원 벡터를 만들어 주고 해당 벡터를 dp 로 놓고 이전 행과의 합을 계속 누적 하고 마지막행에서 최댓값을 구하는 방법으로 코드를 구현 했다

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

이 문제의 경우 전형 적인 다익스트라 알고리즘으로 풀 수 있을거 같았다 그 이유는 첫시작 점이 0 그리고 endPoint인 n-1 까지 가는 것으로 정해졌기에

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().second;
		long long toCost = djikstra_pq.top().first;
		djikstra_pq.pop();

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}

굳이 플로이드  와샬로 전체 의 거리는 구할 필요가 없기 때문이다 

항상 다익스트라에서 쓰는 로직과 비슷하다 일단 StartVertex를 StarVertex까지의 거리가 0이라 두고 큐에다가 넣는다

그후 edgeList에서  startNode와 연결된 모든 노드들과 계산하여 거리를 구한후 priority queue에 넣는다 이를 반복하면 결국에 마지막 노드까지 가는거리가 최단거리로 완성이 된다.

이문제의 경우 단 djikstra를 풀때 조건이 하나가 추가되는데 해당 vertex의 시야값이 1이면 가지 않는 것이다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1234987654321
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> djikstra_pq;
vector<pair<int, long long>> edgeList[300000];
vector<long long> distanceV(300000);
bool canGo[300000] = { 0, };
int n, m;
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().second;
		long long toCost = djikstra_pq.top().first;
		djikstra_pq.pop();

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> canGo[i];
		canGo[i] = !canGo[i];
	}

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		edgeList[from].push_back({ cost,to });
		edgeList[to].push_back({ cost,from });
	}
	distanceV.assign(n , INF);
	djikstraSolution(0);
	if (distanceV[n - 1] >= INF)
		cout << -1;
	else
		cout << distanceV[n-1];
}

전체 코드는 위와 같다

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

이 문제의 경우 전형적인 플로이드 워셜 알고리즘을 사용 하여 구현한다
핵심이 되는  부분은

void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

k즉 i to k , k to j 즉 어떠한 정점 까지 갈때 중간에  거치는 지점이다 즉 계속 거치는 지점을 업데이트 해주면서 최소 거리를 구하는게 플로이드 워셜의 로직이다

#include <iostream>
#define INF 987654321
using namespace std;
int dp[401][401];

int v, e;
void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	int maxValue = INF;
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dp[i][j] == 0;
			else
				dp[i][j] = INF;
			
		}
	}
	for (int i = 0; i < e; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		dp[from][to] = value;
	}

	floyd();

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (dp[i][j] + dp[j][i] < maxValue && !(i==j)) {
				maxValue = dp[i][j] + dp[j][i];
			}
		}
	}
	if (maxValue >= INF) {
		cout << -1;
	}
	else {
		cout << maxValue;
	}
}

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

이 문제의 경우 처음에 이해하기 좀 어려웠었다

이  문제의경우 일단 이경우를 생각 해주어야 한다 길이 2짜리공간에 타일을 넣어서 채울 수 있는 경우의 수는 3이다 4짜리 타일을  채우는 경우의  수는 2가 더있다

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int dp[31] = { 0 };

    dp[0] = 1;
    dp[2] = 3;

    for (int i = 4; i <= n; i++)
    {
        dp[i] = dp[i - 2] * 3; 
        for (int j = 4; j <= i; j += 2)
        {
            dp[i] += dp[i - j] * 2; 
        }
    }

    cout << dp[n];
    return 0;
}

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

이 문제의 경우 점화식을 세우기 빡셌다 이문제의 경우 일단 대충의 로직은

이 상태에서 시작하게 된다 맨위에 파란부분은 수고 그이후의 행들은 해당 숫자를 만드는 데 사용하는 수의 개수를 의미합니다 현재 1행에 숫자 1들이 들어간 이유는 각 수를 만드는데는 자기자신 하나만 필요하기 때문입니다.

자 그리고 다음 행을 봅시다
0을 만드는데는 어차피 0 하나로 밖에 못만드니 

이렇게 채워 줍시다
그다음 2행을 채우게 되면 숫자 2개로 해당 수를 만드는 방법을 봅시다 1은 1+0 과 0+1 로만들 수 있습니다 2는 1+1과 0+2와  2+0으로 만들 수있습니다 우리는 여기서 알수있는게 해당행의 이전행에서의 나자신까지의 합을 모두 더해주면 된다는 것을 알수 있습니다. 0을 선택하게 되면 자동을 2가선택 1을 선택하면 자동으로 1이선택 2를 선택하면 자동으로 0이선택되니 이전행의 자신 열까지의 합을 넣어주면 됩니다

그후 3행은 숫자 3개를 이용하는 것이기에 이전 행에서 2개를 선택한 로직에서 추가로 확장하면 됩니다 숫자 3개로 1을 만드는 방법은 (0+0)+1 , (1+0)+0,  (0+1)+0 이고 2의경우는 이전에 2개를 선택한거에 추가로 해당 수를 제외한 수를 더해주면 자동으로 더해지게 됨으로 이전행의 열들의 값을 더해주면 됩니다

결과적으로 그림이 이렇게 되서 완료가 됩니다.
해당 코드를 구현하면

#include <iostream>
using namespace std;
long long m = 1000000000;
long long dp[204][204];
int main() {
	long long n, k;
	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}


	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[k][n];
}