[백준] 11724, 18111 - C++

18111. 마인크래프트 - C++

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

내 풀이 - 성공

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <set>

#define INF 987654321
#define MAXN 505

using namespace std;

int N, M, B, num;
unordered_map<int, int> heights;
set<int> nums;
int ans[2];

int func(int target, int b)
{
	int total = 0;
	for (auto iter = nums.rbegin(); iter != nums.rend(); iter++) {
		int n = *iter;
		int tmp = 0;
		// 블록 제거
		if (n > target) {
			int h = n - target;
			tmp = 2 * heights[n] * h;
			b += heights[n] * h;
			n = target;
		}
		// 블록 추가
		else if (n < target) {
			// 인벤토리 내에서 해결 가능한지 확인
			int h = target - n;
			if (h * heights[n] <= b) {
				tmp = heights[n] * h;
				b -= heights[n] * h;
				n = target;
			}
			else {
				return INF;
			}
		}
		total += tmp;
	}

	return total;
}

int main()
{
	//freopen("sample_input.txt", "r", stdin);

	scanf("%d %d %d", &N, &M, &B);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &num);
			heights[num] += 1;
			nums.insert(num);
		}
	}

	ans[0] = INF;

	for (int i = 0; i <= 256; i++) {
		int tmp = func(i, B);
		if (ans[0] >= tmp) {
			ans[0] = tmp;
			ans[1] = i;
		}
	}

	printf("%d %d", ans[0], ans[1]);

	return 0;
}

처음에는 최소 시간을 구해야한다는 것에 어렵게 접근했지만 브루트포스로 충분히 풀 수 있는 문제였다

좌표가 중요한 역할을 하진 않아서 높이의 개수를 unordered_map 에 저장해줬다
또한 높이들은 set 에 저장해서 순서대로 접근할 수 있도록 했다

0 ~ 256 까지의 모든 경우를 target 으로 삼고 걸리는 시간을 구했다
인벤토리의 여유를 미리 확보해두기 위해 높이가 큰 애들부터 블록 제거를 했다

조절해야 하는 길이 같은 높이의 개수 걸리는 시간(1 or 2) 를 모두 더해서 return
인벤토리의 블록이 부족하면 불가능한 경우니까 INF 를 return

최솟값으로 갱신해주고 같은 시간이면 더 높은 높이로 갱신해줬다

---

11724. 연결 요소의 개수 - C++

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

내 풀이 - 성공

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>

#define MAXN 1005

using namespace std;

int N, M, u, v;
vector<int> graph[MAXN];
int ans;
int visited[MAXN];

void func(int node) {
	if (visited[node]) return;
	visited[node] = 1;

	for (int i = 0; i < graph[node].size(); i++) {
		func(graph[node][i]);
	}
}

int main()
{
	//freopen("sample_input.txt", "r", stdin);

	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i < N + 1; i++) {
		if (visited[i] == 0) {
			func(i);
			ans++;
		}
	}

	printf("%d", ans);

	return 0;
}

무방향이기 때문에 입력받은 u, v 에 대해 양방향 연결
=> graph[u] 에 v 추가, graph[v] 에 u 추가

visited 를 이용해서 특정 노드와 연결된 모든 노드들은 visited = 1 하며 모든 노드 확인
func 을 돌 때마다 하나의 연결이 생기는 것이므로 ans++