급하게임개발

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

반도체 회로가 얽이지 않기 위해서는
우리는 해당 회로의 LIS를 구하면 된다

이 문제는 내가 이전에 풀었던 LIS 문제를 dp가 아닌 이분탐색으로 푸는 문제이다

해당 이미지를 보고 우리는 LIS즉 이전 인덱스가 현재 인덱스보다 커지지 않게 해주면 된다

이문제의 풀이는 
첫번째로 LIS 배열을 만들어주고 LIS는 무조건 1이상 일것이다 이에 LIS[0]에 arr[0]를 넣어준다

그후 우리는 2

가지 규칙으로 해당 문제를 풀어주면 된다
현재 내가 보는 숫자가 LIS의 가장 나중 인덱스의값보다 크면  그 나중인덱스 + 1 위치에 해당 수를 넣어주고

작을 시에는 해당 LIS 배열에서 해당 수가 들어갈 적절한 위치를 이분탐색으로 찾아서 해당 위치에 해당수를넣어주면된다

#include <iostream>

using namespace std;

int arr[40000];
int lis[40000];

int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;
}
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int j = 0;
	int i = 1;

	lis[0] = arr[0];

	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}

		i += 1;
	}

	cout << j + 1;
}

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

int n;
vector<bool> initial, target;

// 스위치를 누르는 함수
void pressSwitch(vector<bool>& bulbs, int index) {
    if (index > 0) bulbs[index - 1] = !bulbs[index - 1];
    bulbs[index] = !bulbs[index];
    if (index < n - 1) bulbs[index + 1] = !bulbs[index + 1];
}

// 전구를 바꾸는 함수 (첫 번째 전구를 누를지 여부 선택 가능)
int solve(bool pressFirst) {
    vector<bool> bulbs = initial;
    int count = 0;

    // 첫 번째 전구를 누르는 경우
    if (pressFirst) {
        pressSwitch(bulbs, 0);
        count++;
    }

    // 앞에서부터 필요한 곳만 스위치 누르기
    for (int i = 1; i < n; i++) {
        if (bulbs[i - 1] != target[i - 1]) {
            pressSwitch(bulbs, i);
            count++;
        }
    }

    // 결과 확인
    if (bulbs == target) return count;
    return INT_MAX;  // 불가능한 경우
}

int main() {
    cin >> n;
    initial.resize(n);
    target.resize(n);

    // 초기 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        initial[i] = (ch == '1');
    }

    // 목표 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        target[i] = (ch == '1');
    }

    // 두 가지 경우 비교
    int result = min(solve(false), solve(true));

    // 정답 출력
    if (result == INT_MAX) cout << -1;
    else cout << result;
}

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

이 문제를 풀 때 나는 현재 스위치를 기준으로 나와 양옆이 다르면 스위치를 누르려했으나 그게 아니었다 그냥 앞에서 부터 보면서 스위치를 기준으로 이전 전구가 다르면 스위치를 누르는데 0번스위치부터 할건지 1번스위치 부터 누를건지 2개의 경우의 수를 구해서 그중 최솟 값을 구하면 되는 거였다 0번스위치와 1번스위치로 나눈 이유는 0번 스위치의 값을 결정 할수 있는경우 지금 누르거나 다음에 누르거나 두가지 경우의수밖에없기 때문에 우리는 이전 상태를 비교함으로 0번스위치가 1일때의 시작과 0일때의 시작을 모두 비교해보는 것이다

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

처음에 이문제는 dp로 접근했다가 시간초과를 맞고 다시 생각해보았다

나는 처음0번부터 k-1번 인덱스 까지의 초밥의 종류를 저장해 놓고 슬라이딩 윈도우에서 해당 인덱스가 나가거나 들어올 때 isEat배열의 요소를 비교해서 인덱스가 빠질때 isEat이 0이될때는 해당 초밥을 안먹는거니 종류에서 빼주고 들어올 때 1이면 이제 먹는 거니 종류에서 +1해줬다

#include <iostream>
#include <vector>
using namespace std;
vector<int> inputData;
int isEat[3001] = { 0, };
int n, d, k, c;
int GetEat() {
	int total=0;
	for (int i = 0; i <= d+1; i++) {
		if (isEat[i] > 0) {
			total += 1;
		}
	}
	return total;
}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> d >> k >> c;
	inputData.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> inputData[i];
	}
	int ans=0;	

	for (int i = 0; i < k; i++) {
		isEat[inputData[i]] += 1;
	}
	isEat[c] += 1;
	ans = GetEat();
	int maxAns = ans;
	for (int i = 1; i < n; i++) {
		isEat[inputData[i - 1]] -= 1;
		if (isEat[inputData[i - 1]] == 0) {
			ans -= 1;
		}
		isEat[inputData[(i + k-1)%n]]+=1;
		if (isEat[inputData[(i + k - 1) % n]] == 1) {
			ans += 1;
		}
		
		maxAns = max(ans, maxAns);
	}
	cout << maxAns;
}

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

이 문제는 그냥 최소 스패닝 트리 문제인데 조건이 하나가 더추가가됬다 같은 것 끼리만 연결안하고 연결될때마다 간선의 갯수를 측정해준다음 간선의 갯수가 n-1일 때는 다연결된거니 그냥 값 출력해주면 되고 아니면 -1출력해주면 된다

#include <iostream>
#include <queue>
using namespace std;
int n, m;
char arr[1000];
priority_queue<pair<int,pair<int,int>> , vector<pair<int, pair<int, int>>>,greater<pair<int, pair<int, int>>>> inputData;
int parent[1000];
int findParent(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = findParent(parent[x]);
}
bool isSameParent(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);

	if (parentX == parentY)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);

	parent[parentY] = parentX;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		parent[i] = i;
	}
	int u, v, d;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> d;
		inputData.push({ d,{u,v} });
	}
	int ans = 0;
	int countRoad = 0;
	while (!inputData.empty()) {
		int cost = inputData.top().first;
		int from = inputData.top().second.first;
		int to = inputData.top().second.second;
		inputData.pop();
		if (!isSameParent(from, to) && (arr[from]!=arr[to])) {
			uni(to, from);
			ans += cost;
			countRoad += 1;
		}
	}
	if (countRoad == n - 1)
		cout << ans;
	else
		cout << -1;
}

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

이 문제는 일단 부분수열의 합의 모든 경우의 수를 구하는 방법을 알아야한다

부분수열을 굳이 연속되지 않아도 부분수열이기때문에

각 원소가 참여했는지 안했는지를 파악해야해서 n개의 원소를 파악할때 2^n개의 경우의 수를  검사해야 한다.
해당 문제를 푸는 방법

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

해당 문제를 참고 하면된다

#include <iostream>
#include <map>
using namespace std;

int N, S;
int arr[41];
map<int, int> subsum;
long long cnt;

void rightSeq(int mid, int sum) {
    if (mid == N) {
        subsum[sum]++;
        return;
    }

    rightSeq(mid + 1, sum + arr[mid]);
    rightSeq(mid + 1, sum);
}

void leftSeq(int st, int sum) {
    if (st == N / 2) {
        cnt += subsum[S - sum];
        return;
    }

    leftSeq(st + 1, sum + arr[st]);
    leftSeq(st + 1, sum);
}

int main() {
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    rightSeq(N / 2, 0);
    leftSeq(0, 0);

    if (!S) cout << cnt - 1;
    else cout << cnt;

    return 0;
}

전체 코드는 이렇게 된다 부분적으로 한번 보자
일단 2의 20승은 1048576이기 때문에 1초연산을 약 100000000번이라고 가정하면 오바되지 않지만
현재 우리의 문제는 최대 2의40승이기에 1,099,511,627,776번 연산은 1초를 넘어간다

이에 우리는 2의40승에 대하여 2의 20승 2개로 나눠서 연산을 해준다
이에 우리는 우리가 받은 수열을 20개 짜리로 2개로 나눠서한다고 가정한다
그래서 나눈 왼쪽의 모든 부분수열의 합을  map에다가 저장해주고

오른쪽을 연산할때 오른쪽의 부분수열의 합을 연산할때 s-sum이 존재하면 그만큼의 갯수만큼 카운트를 중가시켜주면된다

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

이 문제는 그리드 문제이다 처음에는 input값을 받을 때 인덱스 값을 변경 시켜줬는데 이렇게 풀면틀렸었다
이문제는 일단 데드라인상으로 오름 차순 정렬해준후 이값을 컵라면수의 값에 대한 오름차순 prorityQueue로 만든다 그후  값을 넣어 주면서 현재 size즉 내가 선택한 문제수 가 dealine 값 즉 문제를 풀수 있는 시간보다 많아지면 문제를 포기해야하기 때문에 가장 작은 값을 가지는 값을 pop해준다

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

using namespace std;

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

    vector<pair<int, int>> problems(n);
    for (int i = 0; i < n; i++) {
        cin >> problems[i].first >> problems[i].second; // (데드라인, 컵라면 수)
    }

    // 1. 데드라인 기준 오름차순 정렬
    sort(problems.begin(), problems.end());

    // 2. 최소 힙 사용 (컵라면 개수가 적은 것을 우선 제거)
    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto& p : problems) {
        int deadline = p.first;
        int cupRamen = p.second;

        pq.push(cupRamen); // 현재 문제를 풀어본다고 가정하고 넣음

        // 3. 시간이 초과되면 가장 컵라면 개수가 적은 문제를 버림
        if (pq.size() > deadline) {
            pq.pop();
        }
    }

    // 4. 남아있는 문제들의 컵라면 개수 합산
    int ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }

    cout << ans << '\n';
    return 0;
}