급하게임개발

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

이 문제는 처음에 조건을 잘못 읽었다 처음에 머리<가슴<배 순인 줄알았지

가슴 > 배 , 머리<배 를 만족하는 조건을 찾는 거였다

이에 일단 이문제는 배사이즈를 정해놓고 적절한 머리와 배를 나누는 구간을 찾는 방식으로 문제를 풀어야했다

당연히 배가 머리+가슴 보다 사이즈가 커지게된다면 조건을 만족하게 나눌수 없기에 이부분은 계산 하지 않는다

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

이 함수를 보자 우리는 bellyW 즉 배의 영역의 총합이랑 머리 가슴 영역의 값을 비교해줄것이다
즉 머리 가슴 영역이 bellyw와 조건을 만족 할 수 있도록 즉 머리가 최대한 크지만 배보다 작게 가슴은 최대한 작지만 배보다 큰 idx를 구한다 이 idx를 ans값이라고 하겠다 이것보다 작은값은 다 정답임으로 경우의 수를 반환한다

전체 코드는 아래와 같다

#include <iostream>
using namespace std;

long long arr[1000000];
int n;

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

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

    cin >> n;
    arr[0] = 0;
    long long sum = 0, tmp;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        sum += tmp;
        arr[i] = sum;
    }

    long long ans = 0;
    for (int i = n; i >= 2; i--) {
        long long bellyW = arr[n] - arr[i - 1];
        ans += binaryHeadBelly(i, bellyW);
    }

    cout << ans;
    return 0;
}

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

이 문제는 처음 보고 어떻게 풀어야지라는 생각이 너무들었다 골드 3부터는 여러알고리즘이 섞여 어떻게 딱풀어야지라고 생각이 안나는 거같다

이 문제는 일단 조합으로 우리는 2차원 배열에서 원소를 뽑아줄것이다 원소를 뽑을 때는 1차원 배열이라고 생각해서 뽑아야한다

즉 위표와 같이 0,0 은 0번 0,1은 1번 이라고 생각해야한다 이거를 구하는 방법은 다음과 같다
행/5 + 열%5 를 하면 몇번짼지 우리는 알수 있다 이를 바탕으로 우리는 일차원 배열에서 7개를 뽑은 후 해당 7개의 원소가 서로 이어져 있고 S의 갯수가 4보다 많은지만 검사하면 된다

검사는 우리가 조합으로 뽑은 7개의 원소를 bfs 로 검사한다 즉 bfs로 특정 방향들을 탐색 한다 만약 끊어져있는 부분이 생기면큐에 원소가 들어가지 않을 테니 연속되지 않음을 우리는 알수 있다 전체 코드는 아래와 같다

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

char grid[5][5];
int ans = 0;
bool isConnected(vector<int> selected) {
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int cnt = 1;
    bool isVisited[25] = { false, };
    bool sel[25] = { false, };

    for (int i = 0; i < 7; i++) {
        sel[selected[i]] = true;
    }

    queue<int> bfsQ;
    bfsQ.push(selected[0]);
    isVisited[selected[0]] = true;

    while (!bfsQ.empty()) {
        int cur = bfsQ.front();

        int r = cur / 5;
        int c = cur % 5;

        bfsQ.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5)
                continue;
            int nxt = nr * 5 + nc;


            if (!isVisited[nxt] && sel[nxt]) {
                isVisited[nxt] = true;
                bfsQ.push(nxt);
                cnt++;
            }
        }
    }

    return cnt == 7;
}
void dfs(int start, int count, int sCount, vector<int> selected) {
    if (count == 7) {
        if (sCount >= 4 && isConnected(selected)) {
            ans += 1;
        }
        return;
    }
    if (sCount + (7 - count) < 4)
        return;

    for (int i = start; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;

        selected.push_back(i);

        if (grid[r][c] == 'S') {
            dfs(i + 1, count + 1, sCount + 1, selected);
        }
        else {
            dfs(i + 1, count + 1, sCount , selected);
        }

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

    // 5x5 격자 입력 받기
    for (int i = 0; i < 5; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < 5; j++) {
            grid[i][j] = line[j];
        }
    }

    vector<int> selected;
    dfs(0, 0, 0, selected);
    cout << ans << "\n";

    return 0;
}

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

#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/2887

이 문제의 경우 일반 크루스칼을 이용하여 모든 행성간의 거리를 계산해서 하려고 하다보니 메모리 초과가 발생하였다.
이 문제의 경우 해결방식은 행성의 x,y,z 좌표를 추출한 후 각각의 Vector에 저장한뒤  해당 Vector를 정렬해준 후 차이를 계산하여 그 값을 바탕으로 크루스칼 알고리즘을 돌리는 것이었다

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
vector<pair<int, pair<int, int>>> inputData;
int parent[100001];
vector<pair<int, int>> v[3];
int n;
int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}
bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	cin >> n;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}
	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());
	sort(v[2].begin(), v[2].end());
	int cost = 0;
	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}
	sort(inputData.begin(), inputData.end());
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
		}
	}

	cout << cost;
}

전체 코드는 이렇게 된다 일단 크루스칼의 기본 함수는 알것이라 생각하고 설명을 생략한다

	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}

자 이코드는 사용이유가 우리는 어차피 x간의 차와 y간의 차가 z간의 차가 가장 작은것을 이용해서 문제를 해결할것이므로 이렇게 각각 분리해서 인풋받는다 i는 vertex의 번호다
 그후 정렬을 해주는데 정렬을 하면 각좌표별로 크기별로 정렬이 될것이므로 무조건 나의 다음 vertex와의 거리가 연결 cost가 될거이다 다음다음꺼는 봐줄필요가 없는게 어차피 x값기준으로 만 연산을 할건데 멀리 있으면 연산 할필요가 없기 때문이다

이이후는 일반 크루스칼과 같다

	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}

이런식으로 vertex간 x거리 y거리  z거리를 넣는데 나의 다음거와의 거리만 넣어서 최솟값만 넣는다 중복이 나중에 발생해도 우리는 이 inputData를 정렬할거기 때문에 무조건 짧은 거와 연결된다

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

이 문제는 처음에 그리디를 어떤 방식으로 짜는지가 문제 풀이의 핵심이다

처음에 나는 숫자가나온 갯수에 따라 그리디를 선택 했지만
1700 에서 사용하는 스케줄링 방식은 가장 오랫동안 안쓰는 원소를 교체하는 방식으로 그리디를 작성 한다
이에 큐를 사용하여 나오는 위치를 저장해주고 이를 이용해서 비교해줌으로서 값을 출력하는 방식을 사용했다

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int arr[100];
int concent[100];
queue<int> useCount[101];
bool isUsed[100] = { 0, };
int main() {
	int cnt = 0;
	int input = 0;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		useCount[arr[i]].push(i);
	}
	int i = 0;
	while (input < n && i < k) {
		if (!isUsed[arr[i]]) {
			isUsed[arr[i]] = true;
			concent[input] = arr[i];
			useCount[arr[i]].pop();
			i++;
			input++;
		}
		else {
			useCount[arr[i]].pop();
			i++;
		}
	}
	if (n > k) {
		cout << 0;
		return 0;
	}

	else {
		for (int j = i; j < k; j++) {
			int willPlug = arr[j];
			useCount[arr[j]].pop();
			int outConcnet=-1;
			int notUse=0;
			bool isIn = false;
			for (int l = 0; l < n; l++) {
				if (concent[l] == willPlug) {
					outConcnet = l;
					isIn = true;
					break;
				}
				
			}
			if (!isIn) {
				for (int l = 0; l < n; l++) {
					if (useCount[concent[l]].empty()) {
						outConcnet = l;
						break;
					}
					if (notUse < useCount[concent[l]].front()) {
						notUse = useCount[concent[l]].front();
						outConcnet = l;
					}
				}
			}
			if (concent[outConcnet] != willPlug) {
				concent[outConcnet] = willPlug;
				cnt += 1;
			}
		}
	}

	cout << cnt;
}

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

이 문제의 경우 비트 마스킹 문제 였다 정확히는 비트마스킹을 이용한 브루트 포스가 맞다
비트마스킹을 통해 모든 경우의 수에 대해 구한후 푸는 문제였다
각  재료의 사용 여부를 나타내는 표를 한번 그려보겠다

그릴시 이러한 이미지  가  만들어  진다 즉 사용하면 1 사용하지 않으면 0  위에표는 2번 4번을 사용하고 5개의 재료로 만들수 있는 32개의 경우의 수중 10번 조합이라고 보면된다 그이유는 이진수 01010은 10이기 때문이다
여기 까지 구했으면 우리는 각 조합마다의 재료의 합과 비용의 합을 구한다

그 다음 조건을 만족했을 경우 Map 에다가 가격과 해당 가격에 대한 조합들을  저장해준다 그후 만족한 조합의 최소 가격의 map에서 vector에 조합들이 저장되어 있을 것이고 해당 조합을 오름 차순으로 정렬하여 출력해 주면 된다

#include<bitset>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define INF 200000000
using namespace std;
int n;
map<int, vector<vector<int>>> nutritient_map;
int mp_sum, mf_sum, ms_sum, mv_sum, mc_sum;
int costMax = INF;
struct nutritient {
	int p, f, s, v, c;
};
int main() {
	int mp, mf, ms, mv;
	cin >> n >> mp >> mf >> ms >> mv;
	nutritient arr[15];
	for (int i = 0; i < n; i++) {
		cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
	}
	for (int i = 1; i <  (1 << n); i++) {
		mp_sum = mf_sum = ms_sum = mv_sum = mc_sum = 0;
		vector<int> v;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				mp_sum += arr[j].p;
				mf_sum += arr[j].f;
				ms_sum += arr[j].s;
				mv_sum += arr[j].v;
				mc_sum += arr[j].c;
				v.push_back(j + 1);
			}
		}

		if (mp_sum >= mp && mf_sum >= mf && ms_sum >= ms && mv_sum >= mv) {
			if (costMax >= mc_sum) {
				costMax = mc_sum;
				nutritient_map[costMax].push_back(v);
			}
		}
	}
	if (costMax == INF) {
		cout << -1 << endl;
	}
	else {
		cout << costMax << endl;
		sort(nutritient_map[costMax].begin(), nutritient_map[costMax].end());
		for (int i : nutritient_map[costMax][0]) {
			cout << i << " ";
		}
	}
}

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

이 문제의 경우 브루트 포스긴 하나 모든 경우의 수에 대해 bfs를 이용해서 푸는 문제였다 bfs를 브루트포스하여 푸는 문제니 부르트포스 문제일 수도 있고 bfs 문제일 수도 있다 이문제의 경우 bfs를 구현할 줄 알면 큰  문제가 없다 본인의 경우 2%의  오류가 났었는데 해당 이유는 처음 bfs를 실행할 때 해당 위치가 'W'인지를 검사 하지 않아서 발생 했었다

#include<iostream>
#include<queue>
using namespace std;
int n, m;
char arr[50][50];
int isVisited[50][50] = { 0, };
int maxLength=0;
queue<pair<int, int>>bfsQ;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m && !isVisited[x][y] && arr[x][y]=='L')
		return true;
	else
		return false;
}
void bfs(int sx, int sy) {
	bfsQ.push({ sx,sy });
	isVisited[sx][sy] = 1;
	while (!bfsQ.empty()) {
		int sx = bfsQ.front().first;
		int sy = bfsQ.front().second;
		int distance = isVisited[sx][sy];
		bfsQ.pop();
		for (int i = 0; i < 4; i++) {
			if (canGo(sx + dx[i], sy + dy[i])) {
				bfsQ.push({sx + dx[i],sy + dy[i]});
				isVisited[sx + dx[i]][sy + dy[i]] = distance + 1;
			}
		}
	}
}
int getMaxValue() {
	int maxValue=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			maxValue=max(maxValue, isVisited[i][j]);
		}
	}
	return maxValue-1;
}
void InitIsVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			isVisited[i][j] = 0;
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (canGo(i, j)) {
				bfs(i, j);
				maxLength = max(maxLength, getMaxValue());
				InitIsVisited();
			}
		}
	}
	cout << maxLength;
}