급하게임개발

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

이 문제는 처음에는 역 다익스트라를 면접장에서 구해서 최소 면접점을 구해서 했는데 시간 복잡도가 나왔다

이문제를 풀면서 처음안건데 멀티소스다익스트라라는 것이 있었다 이 알고리즘은 다익스트라의 시작점에 여러개를 넣고 시작하는데 이때 distacneV 벡터에는 각 시작점들에서 부터 그지점까지 가는곳의 최솟 값이 저장된다 즉 어디서 왔는지에 대해서는 모르지만 여러시작점들중 나까지 오는데의 최소 거리는 알수 있다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 50000000001

int n, m, k;
vector<pair<int, long long>> edgeList[100001];  // 1번부터 n번까지 사용 (문제 constraints에 따라)
vector<long long> dist;  // 각 도시까지의 최단 거리

// 멀티 소스 다익스트라: 여러 시작점을 동시에 처리
void multiSourceDijkstra(const vector<int>& startNodes) {
    dist.assign(n + 1, INF);
    // (거리, 노드)를 저장하는 최소 힙
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    // 모든 면접 장소를 초기 노드로 넣고 거리를 0으로 설정
    for (int node : startNodes) {
        dist[node] = 0;
        pq.push({ 0, node });
    }

    while (!pq.empty()) {
        int cur = pq.top().second;
        long long curCost = pq.top().first;
        pq.pop();

        if (curCost > dist[cur])
            continue;

        // 인접 노드 업데이트
        for (auto& edge : edgeList[cur]) {
            int next = edge.first;
            long long nextCost = edge.second;
            if (dist[next] > curCost + nextCost) {
                dist[next] = curCost + nextCost;
                pq.push({ dist[next], next });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    // 도로 정보를 입력받으며, 문제의 조건에 맞게 간선의 방향을 반대로 저장합니다.
    int from, to;
    long long cost;
    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        // 인터뷰 장소로의 최단 경로를 구하기 위해 간선의 방향을 반대로 저장
        edgeList[to].push_back({ from, cost });
    }

    vector<int> interviewLocations(k);
    for (int i = 0; i < k; i++) {
        cin >> interviewLocations[i];
    }

    // 멀티 소스 다익스트라 실행
    multiSourceDijkstra(interviewLocations);

    // 각 도시에서 면접 장소까지의 최단 거리가 최대인 도시를 찾습니다.
    int answerCity = 0;
    long long maxDistance = -1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxDistance) {
            maxDistance = dist[i];
            answerCity = i;
        }
    }

    cout << answerCity << "\n" << maxDistance << "\n";

    return 0;
}

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

이 문제는 dp를 활용한 0-1 냅색 문제이다 즉 어떠한 원소를 사용할지 말지에 대해서 dp로 계속 값을 갱신해주는 것이다

예제를 표로 나면 이렇게 된다  

여기를 주목해보자 30과 10까지만 사용해서 5초를 만들었을의 최대무게는 40이였다 하지만 이제 20을 넣는다고 가정하자
여기서 5초로는 40밖에 이전에는 만들지 못했는데 20이 들어오게되면서 30과 10으로 만들었던 3초 더하기 현재 2초 5초를 만들면서 60이 된다

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

using namespace std;
int n, m;
int memory[101];
int cost[101];

// i번째 앱을 선택 했을 때의 비용 j dp[i][j]에는 이때의 최대 무게가 들어감
int dp[101][10001];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> memory[i];
	}
	int total = 0;
	for (int j = 1; j <= n; j++) {
		cin >> cost[j];
		total += cost[j];
	}
	int ans = 100001;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= total; j++) {
			// j가 현재 cost[i] 내가 넣으려는 cost보다 작으면 넣을 수 없으니 이전 값 사용
			if (j < cost[i])
				dp[i][j] = dp[i - 1][j];
			// 아닐 때느 나 이전까지만 넣은 애들 중에 현재 계산하려는 cost에서 나의 cost를 빼고 나의 무게를 더한거
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);

			if (dp[i][j] >= m)
				ans = min(ans, j);
		}
	}
	
	cout << ans;
}

코드로는 이렇게 된다

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

이 문제는 처음에 플로이드로 풀다가 시간초과  나서  djikstra로 변경하였다 이문제는 그냥 다익스트라를 세번 돌리면 되는데

       int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
       int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

이렇게 실제 거리와 g_h를 지나는 거리와 똑같다면 g -> h를 지나간다고 판별 할 수 있으니
이를 이용해서 목적지까지의 거리가 같으면 priority_queue에 넣은 후 차례로  pop하면 되는 문제였다

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

using namespace std;

#define INF 1000000001

int t, n, m, d;
int s, g, h;
vector<pair<int, int>> edgeList[2001];
vector<int> distance_v;

void dijkstra(int start, vector<int>& dist) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist.assign(n + 1, INF);
    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int cur_cost = pq.top().first;
        int cur_vertex = pq.top().second;
        pq.pop();

        if (cur_cost > dist[cur_vertex])
            continue;

        for (auto next : edgeList[cur_vertex]) {
            int next_vertex = next.first;
            int next_cost = next.second;

            if (dist[next_vertex] > cur_cost + next_cost) {
                dist[next_vertex] = cur_cost + next_cost;
                pq.push({ dist[next_vertex], next_vertex });
            }
        }
    }
}

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

    cin >> t;
    while (t--) {
        cin >> n >> m >> d;
        cin >> s >> g >> h;

        for (int i = 0; i <= n; i++) {
            edgeList[i].clear();
        }

        int g_h_cost = 0;
        for (int i = 0; i < m; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
            edgeList[from].push_back({ to, cost });
            edgeList[to].push_back({ from, cost });

            if ((from == g && to == h) || (from == h && to == g)) {
                g_h_cost = cost; // g-h 간선의 비용 저장
            }
        }

        // 다익스트라 실행
        vector<int> dist_s(n + 1), dist_g(n + 1), dist_h(n + 1);
        dijkstra(s, dist_s);
        dijkstra(g, dist_g);
        dijkstra(h, dist_h);

        priority_queue<int, vector<int>, greater<int>> destination_pq;
        for (int i = 0; i < d; i++) {
            int dest;
            cin >> dest;

            int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
            int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

            if (dist_s[dest] == route1 || dist_s[dest] == route2) {
                destination_pq.push(dest);
            }
        }

        // 결과 출력
        while (!destination_pq.empty()) {
            cout << destination_pq.top() << " ";
            destination_pq.pop();
        }
        cout << endl;
    }
}

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

이 문제는 m 으로 입력받아야하는데 n으로 입력받아서 로직으로는 맞는데 계속 틀린값이 나와서 멘탈나갈뻔했다 일단 이문제는 그냥 이제 i->j 로갈때의 첫번째 노드를 저장해놓는 배열을 따로 만들어 놓고 해당 배열을 통해 지속적으로 업데이트 해주면 되는 문제였다

#include <iostream>
using namespace std;
#define INF 200000000

// 여기는 경로 코스트 저장
int arr[201][201];
// 여기는 j로 가는 가장 먼저 방문해야 할 곳 저장
int arr2[201][201];

int n, m;

int main() {
    cin >> n >> m;
    int t1, t2, t3;

    // 거리 배열 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                arr[i][j] = 0;
            }
            else {
                arr[i][j] = INF;
                arr2[i][j] = j;  // 초기 방문 노드를 j로 설정
            }
        }
    }

    // 간선 정보 입력
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        arr[t1][t2] = t3;
        arr[t2][t1] = t3;
        arr2[t1][t2] = t2;
        arr2[t2][t1] = t1;
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                    arr2[i][j] = arr2[i][k]; // i -> j로 가는 첫 방문 노드 업데이트
                }
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) cout << "- ";
            else cout << arr2[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

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

이 문제는전형 적인 dp문제이다 점화식만 세우면 문제되는 부분은 없었다 점화식은 dfs랑 비슷하게 생각하면되지만 
이문제의 핵심은 현재 칸에 왔을 때 내가 갈 수 있는 칸이 더많은 칸으로 가는거를 골라야한다 .

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int arr[501][501] = { 0, };
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> inputData;
int n;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dp[501][501];
bool canGo(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		return true;
	}
	return false;
}
int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			inputData.push({ arr[i][j],{i,j} });
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = 1;
		}
	}
	while (!inputData.empty()) {
		int curCost = inputData.top().first;
		int curX = inputData.top().second.first;
		int curY = inputData.top().second.second;
		inputData.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];
			
			if (canGo(nextX, nextY) && curCost < arr[nextX][nextY]) {
				dp[curX][curY] = max(dp[nextX][nextY] + 1, dp[curX][curY]);
			}
		}
	}

	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}

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

이 문제는 dp 와 비트마스킹을 섞은 문제이다 일단 이문제는 이전
https://www.acmicpc.net/problem/10844

10844번 문제를 풀었을 경우 쉬웠을 것이다

일단 우리는 작은 단계에서 부터 검증을 하자 일단 자릿수가 2일때의 계단수를 구해보자

길이 가 3일때는 어떻게 될까 우리는 이전 길이가 2인계단수에서 답을 구할수 있다
자리가 3이고 첫시작수가 2일때 우리는 이전 1과 3에서 값을 가져와서 할수있다 이에

            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }

이렇게 된다 k는 현재 어떤수가 사용되었는지를 비트마스킹으로 나타낸것이다 우리는 이후에 모두 사용된 1023일때만의 값을 구해서 답을 구할 것이다

#include <iostream>
using namespace std;

const int mod = 1e9;
int dp[100][10][1024]; // (자리수, 마지막 숫자, 방문한 숫자 상태)

int main() {
    int n;
    cin >> n;

    // 초기 상태 설정
    for (int j = 1; j <= 9; j++) {
        dp[0][j][1 << j] = 1;  // 첫 번째 자리는 1~9만 가능 (0은 불가능)
    }

    // DP 점화식 수행
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < 1024; k++) {
                if (dp[i][j][k] == 0) continue;

                int next;
                // 다음 숫자가 j+1일 때
                if (j < 9) {
                    next = k | (1 << (j + 1));
                    dp[i + 1][j + 1][next] = (dp[i + 1][j + 1][next] + dp[i][j][k]) % mod;
                }

                // 다음 숫자가 j-1일 때
                if (j > 0) {
                    next = k | (1 << (j - 1));
                    dp[i + 1][j - 1][next] = (dp[i + 1][j - 1][next] + dp[i][j][k]) % mod;
                }
            }
        }
    }

    // 정답 계산 (n번째 자릿수에서 0~9까지 모든 숫자를 포함하는 경우)
    int answer = 0;
    for (int j = 0; j <= 9; j++) {
        answer = (answer + dp[n - 1][j][1023]) % mod;
    }

    cout << answer << endl;
    return 0;
}

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;
}