취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26935번 문제인 Släktträffen이다.
문제는 아래 링크를 확인하자.

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

이 문제는 주어지는 M개의 노드의 LCA(Lowest Common Ancestor)를 구하는 문제이다.

DFS를 이용한 트리DP를 이용해 각 노드를 루트로 하는 서브트리에 포함된 "M개의 노드에 포함되는 노드"의 개수를 구하고, 그 값이 M인 노드 중 가장 깊은 노드를 출력해 문제를 해결할 수 있다.

위와 같이 해결하지 않더라도 각 노드에서 DFS를 시도해 해당 노드를 루트로 하는 서브트리의 노드의 개수와 포함하는 "M개의 노드에 포함되는 노드"의 개수를 각각 구한 뒤, 포함하는 "M개의 노드에 포함되는 노드"가 M과 같은 서브트리 중 노드의 개수가 가장 적은 서브트리의 루트를 출력하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int N, M;
vector<int> G[21];
int num[21];
bool chk = 1;

int dfs(int cur) {
	int ret = num[cur];
	for (auto& nxt : G[cur]) {
		ret += dfs(nxt);
	}

	if (ret == M && chk) cout << cur, chk = 0;

	return ret;
}

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

	cin >> N >> M;
	for (int cur = 1; cur <= N; cur++) {
		int par; cin >> par;
		G[par].emplace_back(cur);
	}

	for (int m = 0; m < M; m++) {
		int x; cin >> x;
		num[x]++;
	}

	dfs(0);
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26934번 문제인 The Bus Card이다.
문제는 아래 링크를 확인하자.

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

먼저 필요금액을 이용해 100단위의 값의 목표금액을 구해주자. 예를 들어 필요금액이 180이면 목표금액은 200이, 필요금액이 300이면 목표금액은 300이, 필요금액이 1234면 목표금액은 1300이 된다. 이는 필요금액을 100으로 나눈 나머지가 0인지 아닌지를 이용한 조건문으로 구해낼 수 있다. 

위에서 구한 목표금액을 충전하는 데에 필요한 충전 횟수는 그리디한 전략으로 구해낼 수 있다. 구체적으로, 가능한 한 500을 많이 충전한 후 남은 금액을 100과 200을 이용해 충전하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int K;
int arr[5] = { 0,1,1,2,2 };

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

	cin >> K;
	if (K % 100) K = K / 100 + 1;
	else K = K / 100;

	cout << K / 5 + arr[K % 5];
}