취미로 코딩하기

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

이번에 볼 문제는 백준 25498번 문제인 핸들 뭘로 하지이다.
문제는 아래 링크를 확인하자.

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

루트 노드로부터 주어진 트리를 따라 DFS를 진행하며, 기존 정답후보로 찾아둔 문자열과 비교해 사전순으로 더 늦은 문자열을 생성할 수 있다면 해당 문자열을 계속 추적해나가고 그렇지 않다면 해당 방향으로의 탐색을 중단하는 식으로 문제를 해결하자.

문자열의 중간서부터 다른 문자로 교체해 새로운 답의 후보를 얻을 때, 답으로 유지되는 앞부분의 부분문자열을 복사하는 작업을 하면 시간복잡도가 늘어 문제를 해결하기 어려울 것으로 보인다. 해당 부분을 복사하는 대신 새로운 답의 후보에 포함되지 않는 문자를 뒤에서부터 하나씩 지워나가는 식으로 구현하면 시간복잡도가 늘지 않으므로 이렇게 문제를 해결해주자. (하나의 문자를 지우는 작업은 많아야 O(N)번 하게 되기 때문이다.)

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

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

int N;
string s;
vector<int> G[500001];
string ans;

void dfs(int cur, int par, int lv) {
	if (ans.length() == lv) ans += s[cur];
	else if (ans[lv] < s[cur]) {
		while (ans.length() > lv) ans.pop_back();
		ans += s[cur];
	}
	else if (ans[lv] > s[cur]) return;

	for (auto& nxt : G[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, lv + 1);
	}
}

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

	cin >> N >> s;
	s = " " + s;

	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	dfs(1, 0, 0);

	cout << ans;
}

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

이번에 볼 문제는 백준 25496번 문제인 장신구 명장 임스이다.
문제는 아래 링크를 확인하자.

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

만드는 장신구의 개수를 최대화하는 것이 목적이므로, 주어진 만들 수 있는 장신구 중 피로도가 적게 오르는 장신구부터 차례대로 만드는 것이 언제나 최선의 전략이 된다.

주어진 각 장신구를 만들 때 오르는 피로도를 크기순으로 정렬하고, 그 값이 작은 장신구부터 제작하는 과정을 시뮬레이션해 문제를 해결하자.

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

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

int P, N;
int arr[1000];
int ans;

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

	cin >> P >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	for (int i = 0; i < N && P < 200; i++) {
		P += arr[i];
		ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 25497번 문제인 기술 연계마스터 임스이다.
문제는 아래 링크를 확인하자.

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

주어지는 키입력을 순서대로 읽어나가며 주어진 입력을 따라 시뮬레이션을 돌려 스킬의 성공 횟수를 구해 문제를 해결하자.

구체적으로, 이번 차례에 입력된 키가 'L' 또는 'S'라면 해당 키가 입력으로 들어온 횟수를 늘려주고, 'R'또는 'K'라면 대응되는 사전 기술의 횟수를 1회 소모하며 스킬을 성공적으로 사용(횟수가 없다면 이후의 키입력을 무시), 그 외의 경우는 스킬을 성공적으로 1회 사용하는 것과 같은 과정을 시뮬레이션해 문제를 해결해주자. 이는 반복문을 이용해 구현할 수 있다.

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

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

int slen;
string s;

int cnt[128];
int ans;

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

	cin >> slen >> s;
	for (auto& l : s) {
		if (l == 'S' || l == 'L') cnt[l]++;
		else if (l == 'K') {
			if (cnt['S']) cnt['S']--, ans++;
			else break;
		}
		else if (l == 'R') {
			if (cnt['L']) cnt['L']--, ans++;
			else break;
		}
		else ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 25499번 문제인 Tipover Transform이다.
문제는 아래 링크를 확인하자.

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

주어지는 모든 블록은 결국 모두 적어도 한 번씩은 밟고 지나가야 함을 관찰하자.

위 관찰에 따라, 각 블록이 쓰러진 방향에 대하여 해당 블록의 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수를 이전 블록의 쓰러진 방향에 따른 각 상태의 왼쪽 끝까지 도달하기 위해 필요한 큐브블록의 수를 이용해 나타낼 수 있음을 알 수 있다. 즉, 이전 블록의 (쓰러진 방향에 따른) 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수와 현재 블록의 (쓰러진 방향에 따른) 왼쪽 끝까지 도달하기 위해 필요한 최소 큐브블록 개수 사이에는 점화관계가 존재함을 알 수 있다.

이와 같은 점화관계를 이용해 dp로 문제를 해결해주자.

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

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

int N, M;
pair<int, int> seg[300001][3]; // 0: 서있음, 1: 왼쪽쓰러짐, 2: 오른쪽쓰러짐
int dp[300001][3];
int ans = 1000000007;

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

	seg[0][0] = seg[0][1] = seg[0][2] = { 0,0 };

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int h; cin >> h;
		if (h) {
			M++;
			seg[M][0] = { i,i };
			seg[M][1] = { i - h,i - 1 };
			seg[M][2] = { i + 1,i + h };
		}
	}

	for (int i = 1; i <= M; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = 1000000007;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (seg[i - 1][j].second < seg[i][k].first) dp[i][k] = min(dp[i][k], dp[i - 1][j] + (seg[i][k].first - seg[i - 1][j].second - 1));
			}
		}
	}

	ans = min(dp[M][0] + (N - seg[M][0].second), dp[M][1] + (N - seg[M][1].second));
	if (seg[M][2].second <= N) ans = min(ans, dp[M][2] + (N - seg[M][2].second));

	cout << ans;
}

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

이번에 볼 문제는 백준 25500번 문제인 무자비한 최단 경로이다.
문제는 아래 링크를 확인하자.

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

문제에 주어진 그래프를 그대로 모델링해 최단경로 알고리즘(dijkstra 등)을 이용해 문제를 해결하고 싶으나, 그러기에는 간선이 너무 많아 시간이 너무 오래걸린다. 묘사할 필요가 없는 에지(해당 에지를 제외하더라도 최단거리가 변하지 않는 에지)를 제외해 에지의 수를 O(N)개로 줄여 그래프를 모델링해 문제를 해결해보자.

x와 y좌표의 경우, 모든 두 마을 사이의 x좌표의 차이와 y좌표의 차이 거리의 두 개의 에지가 모두 있는 그래프를 기본적으로 생각할 수 있다. (모두 그려두면 그중 값이 작은 에지를 최단거리를 탐색할 때 자연스레 이용할 것이기 때문이다.) 이 때, 어떤 세 마을의 x좌표 x1, x2, x3에 대하여 x1<x2<x3이 성립하면 x1과 x3을 잇는 x방향의 차의 에지는 지워져도 대신 x1에서 x2까지 x좌표 차만큼의 가중치의 에지와 x2에서 x3까지 x좌표 차만큼의 가중치의 에지를 이용해 여전히 같은 가중치로 이동할 수 있음을 관찰하자.

위의 관찰을 일반화하면 x좌표 사이의 거리에 관한 모든 에지는 x좌표 오름차순으로 인접한 두 마을 사이의 에지만으로, y좌표 사이의 거리에 관한 모든 에지는 y좌표 오름차순으로 인접한 두 마을 사이의 에지만으로 전부 표현할 수 있음을 알 수 있다.

z좌표의 경우, z를 K로 나눈 나머지가 p인 지점과 K-p(단, p가 0일 경우 0)인 지점 사이의 간선을 긋는 것을 먼저 생각해볼 수 있다. 그러나 해당 쌍을 직접 모두 잇는다면 에지가 O(N^2)개 생길 수 있으므로 이 또한 최적화를 해주어야 한다.

z를 K로 나눈 나머지가 p인 지점이 모이는 가상의 노드를 만들어 각 나머지가 p인 지점에서 해당 노드로의 가중치 z의 방향에지를 이어주고, 이 노드에서 나머지가 K-p(단, p가 0일 경우 0)인 각 노드로의 방향에지를 이어주면 에지를 O(N)개로 z방향의 모든 이동을 표현할 수 있게 된다.

위와 같이 그래프를 모델링하면 주어진 문제의 상황을 O(N)개의 에지로 이루어진 그래프로 모델링할 수 있게 된다. 이 그래프 위에서 dijkstra 등의 최단경로 알고리즘을 이용해 문제를 해결하자.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef unsigned int uint;

int N, K;
pair<uint, int> vecX[200000];
pair<uint, int> vecY[200000];
vector<pair<int,uint>> G[400000];
uint dist[400000];

void dijkstra() {
	priority_queue<pair<uint, int>, vector<pair<uint,int>>, greater<>> pq;
	dist[0] = 1;
	pq.push(make_pair(1, 0));

	while (!pq.empty()) {
		int cur = pq.top().second; uint d = pq.top().first; pq.pop();
		if (dist[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first; uint dd = p.second;
			if (dist[nxt] == 0 || dist[cur] + dd < dist[nxt]) {
				dist[nxt] = dist[cur] + dd;
				pq.push(make_pair(dist[nxt], nxt));
			}
		}
	}
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		uint x, y, z; cin >> x >> y >> z;
		vecX[i] = { x,i };
		vecY[i] = { y,i };
		G[i].emplace_back(make_pair(z % K + 200000, z));
		G[(K - z % K) % K + 200000].emplace_back(make_pair(i, z));
	}

	sort(vecX, vecX + N), sort(vecY, vecY + N);
	for (int i = 1; i < N; i++) {
		int n1 = vecX[i - 1].second, n2 = vecX[i].second; uint d = vecX[i].first - vecX[i - 1].first;
		G[n1].emplace_back(make_pair(n2, d));
		G[n2].emplace_back(make_pair(n1, d));
	}
	for (int i = 1; i < N; i++) {
		int n1 = vecY[i - 1].second, n2 = vecY[i].second; uint d = vecY[i].first - vecY[i - 1].first;
		G[n1].emplace_back(make_pair(n2, d));
		G[n2].emplace_back(make_pair(n1, d));
	}
	
	dijkstra();

	for (int i = 0; i < N; i++) cout << dist[i] - 1 << '\n';
}

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

이번에 볼 문제는 백준 25495번 문제인 에어팟이다.
문제는 아래 링크를 확인하자.

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

에어팟을 주어진 핸드폰에 연결하려고 시도할 때마다 배터리의 소모량이 어떻게 변하는지를 직접 시뮬레이션을 돌리는 코드를 작성해 문제를 해결하자.

이는 이전에 연결했던 핸드폰이 무엇인지 나타내는 변수와 이전 차례에 소모한 배터리의 양이 얼마인지를 저장하는 변수, 그리고 현재 소모된 배터리의 양이 얼마인지를 저장하는 변수의 세가지 변수와 반복문과 조건문을 이용해 간단히 구현할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int connected = 0, prv = 0, battery = 0;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x == connected) {
			battery += prv * 2;
			prv *= 2;
		}
		else {
			connected = x;
			battery += 2;
			prv = 2;
		}

		if (battery > 99) connected = 0, prv = 0, battery = 0;
	}

	cout << battery;
}