취미로 코딩하기

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

이번에 볼 문제는 백준 28281번 문제인 선물이다.
문제는 아래 링크를 확인하자.

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

X의 값은 변하지 않으므로, 문제에서 구하는 값을 최소화하기 위해서는 "붙어있는 두 양말가격의 합"을 최소화해야 함을 알 수 있다.

양말의 가격을 배열에 저장해두고 반복문을 이용해 인접한 두 값의 합을 전수조사해 "붙어있는 두 양말가격의 합"을 계산하고 문제를 해결하자. 배열을 사용하지 않고 해결하는 풀이 또한 존재하는데, 이를 생각하는 것은 읽는이에게 맡긴다.

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

#include <iostream>
using namespace std;

int N, X;
int arr[100000];
int mn = 1000000007;

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

	cin >> N >> X;
	for (int i = 0; i < N; i++) cin >> arr[i];
	N--;
	for (int i = 0; i < N; i++) mn = min(mn, arr[i] + arr[i + 1]);

	cout << mn * X;
}

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

이번에 볼 문제는 백준 28282번 문제인 운명이다.
문제는 아래 링크를 확인하자.

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

양발에 다른 색의 양말을 신을 경우의 수는 (양말을 신을 전체 경우의 수) - (양발에 같은 색의 양말을 신을 경우의 수)로 계산할 수 있다.

양말을 신을 전체 경우의 수는 왼발양말 X개 중 하나와 오른발양말 X개 중 하나를 고르는 경우의 수와 같으므로 $X^2$이다.

양발에 같은 색의 양말을 신을 경우의 수는 각 색상별로 왼발양말의 개수와 오른발양말의 개수를 곱한 값을 더하는 것으로 계산할 수 있다.

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

#include <iostream>
using namespace std;
typedef long long ll;

ll X, K;
ll L[10001], R[10001];
ll ans;

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

	cin >> X >> K;
	for (int i = 0; i < X; i++) {
		int x; cin >> x;
		L[x]++;
	}
	for (int i = 0; i < X; i++) {
		int x; cin >> x;
		R[x]++;
	}

	ans = X * X;
	for (int i = 1; i <= K; i++) ans -= L[i] * R[i];

	cout << ans;
}

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

이번에 볼 문제는 백준 28283번 문제인 해킹이다.
문제는 아래 링크를 확인하자.

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

각 컴퓨터를 해킹했을 때 얻을 수 있는 돈은 해킹 후 각 컴퓨터에 보안 시스템이 설치되는 시점과 A값을 이용해 구할 수 있다. 이 값들을 모두 구한 뒤 문제를 해결하자.

해킹 후 각 컴퓨터에 보안 시스템이 언제 설치되는지는 BFS를 이용하면 빠르게 계산해낼 수 있다.

어떤 컴퓨터에 보안 시스템이 설치되지 못하더라도 해당 컴퓨터의 A값이 0이면 해당 컴퓨터를 이용해 돈을 무한히 벌 수 없음에 유의하자.

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, M, X, Y;
vector<int> G[500001];
ll dist[500001];
ll cost[500001];
queue<int> que;
priority_queue<ll> val;
ll ans;

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

	cin >> N >> M >> X >> Y;
	for (int i = 1; i <= N; i++) cin >> cost[i];
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	while (Y--) {
		int x; cin >> x;
		dist[x] = 1;
		que.push(x);
	}

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		val.push((dist[cur] - 1) * cost[cur]);
		for (auto& nxt : G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}

	for (int i = 1; i <= N; i++) {
		if (!dist[i]) {
			if (cost[i]) {
				cout << -1;
				return 0;
			}
			else val.push(0);
		}
	}

	while (X--) {
		ans += val.top();
		val.pop();
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 28284번 문제인 스터디 카페이다.
문제는 아래 링크를 확인하자.

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

벌 수 있는 최대 수익은 각 날에 스터디 카페에 찾아온 이용자 K명을 비용이 비싼 차례대로 K개의 좌석에 앉힐 때임을 쉽게 알 수 있다. 다만 모든 날에 대하여 이를 시뮬레이션하는 것으로는 문제를 충분히 해결할 수 없다. 10억일동안의 각 날에 대해 직접 계산하기에는 제한시간이 부족하기 때문이다.

위의 문제를 효율적으로 해결하기 위해 스터디 카페에 찾아오는 인원이 바뀌는 날들을 기준으로 기간을 나누는 방법을 생각하자. 이와 같이 나눌 경우, 각 나눠진 기간에 벌 수 있는 최대 수익은 (기간에 포함된 날의 수) * (해당 기간의 각 날에 벌 수 있는 최대 수익)과 같이 구할 수 있음은 쉽게 관찰할 수 있다. 또한 하루의 최대 수익은 그 날 찾아오는 인원이 정해지면 변하지 않으므로 prefix sum을 이용해 전처리해 두면 프로그램을 빠르게 동작하게 할 수 있다.

최소 비용 또한 비슷한 방법으로 구해 문제를 해결하자.

문제의 답이 32비트 정수 자료형으로 표현할 수 있는 범위를 넘을 수 있음에 유의하자.

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int N, M;
ll cost1[500000], cost2[500000];
ll oldT, curcost; int cidx = -1;
vector<pair<ll, int>> sched;

ll ans1, ans2;

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> cost1[i];
	sort(cost1, cost1 + N, greater<>());
	for (int i = 0; i < N; i++) cost2[i] = cost1[N - i - 1];
	for (int i = 1; i < N; i++) cost1[i] += cost1[i - 1];
	for (int i = 1; i < N; i++) cost2[i] += cost2[i - 1];

	while (M--) {
		int S, E; cin >> S >> E;
		sched.emplace_back(make_pair(S, 1));
		sched.emplace_back(make_pair(E + 1, -1));
	}

	sort(sched.begin(), sched.end());

	for (auto& p : sched) {
		if (cidx >= 0) ans1 += (p.first - oldT) * cost1[cidx], ans2 += (p.first - oldT) * cost2[cidx];
		oldT = p.first;
		cidx += p.second;
	}

	cout << ans2 << ' ' << ans1;
}

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

이번에 볼 문제는 백준 28285번 문제인 육각형 순회이다.
문제는 아래 링크를 확인하자.

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

주어진 육각형을 순회하는 회로는 다양하게 존재한다. 이 중 규칙적으로 생성하기 쉬운 방법을 찾아 문제를 해결하자.

특히, 주어지는 시작점 대신 고정된 하나의 위치(글쓴이의 경우 마지막 행 첫 번째 칸)에서 출발하는 경로 중 문제의 조건을 만족하는 것을 하나 찾고 이를 따라 주어진 칸에서 출발해 한 바퀴를 도는 경로를 출력하면 문제를 간편하게 해결할 수 있다.

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

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

int N, R, C, r, c;
deque<char> dqL, dqR;
int initX, initY;

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

	cin >> N >> R >> C;
	r = N * 2 - 1, c = 1;
	if (N < 4) {
		if (N == 3) {
			dqR.push_back('Q');
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('E');
			dqR.push_back('D');
			dqR.push_back('Z');
			dqR.push_back('Z');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('C');
			dqR.push_back('Z');
			dqR.push_back('Z');
			dqR.push_back('A');
			dqR.push_back('A');
		}
		else {
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('Z');
			dqR.push_back('A');
		}
	}
	else {
		dqL.push_front('A');
		int n = N;
		while (n > 3) {
			for (int i = 1; i < n; i++) dqR.push_back('Q');
			for (int i = 1; i < n; i++) dqR.push_back('E');
			for (int i = 2; i < n; i++) dqR.push_back('D');
			dqR.push_back('Z');
			for (int i = 3; i < n; i++) dqR.push_back('A');
			for (int i = 2; i < n; i++) dqR.push_back('Z');
			for (int i = 2; i < n; i++) dqR.push_back('C');
			dqR.push_back('E');

			for (int i = 2; i < n; i++) dqL.push_front('A');
			for (int i = 1; i < n; i++) dqL.push_front('Z');
			for (int i = 1; i < n; i++) dqL.push_front('C');
			dqL.push_front('E');
			for (int i = 2; i < n; i++) dqL.push_front('Q');
			for (int i = 2; i < n; i++) dqL.push_front('E');
			for (int i = 3; i < n; i++) dqL.push_front('D');
			dqL.push_front('Z');

			n -= 2;
		}

		if (n == 3) {
			dqR.push_back('Q');
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('E');
			dqR.push_back('D');
			dqR.push_back('Z');
			dqR.push_back('Z');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('C');
			dqR.push_back('Z');
			dqR.push_back('Z');
			dqR.push_back('A');
		}
		else {
			dqR.push_back('Q');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('E');
			dqR.push_back('C');
			dqR.push_back('Z');
		}

		while (!dqL.empty()) {
			dqR.push_back(dqL.front());
			dqL.pop_front();
		}
	}

	while (r != R || c != C) {
		char& cur = dqR.front();
		if (cur == 'A') c--;
		else if (cur == 'D') c++;
		else if (cur == 'Q') {
			if (r <= N) c--;
			r--;
		}
		else if (cur == 'E') {
			if (r > N) c++;
			r--;
		}
		else if (cur == 'Z') {
			if (r >= N) c--;
			r++;
		}
		else {
			if (r < N) c++;
			r++;
		}

		dqR.push_back(cur);
		dqR.pop_front();
	}

	while (!dqR.empty()) {
		cout << dqR.front();
		dqR.pop_front();
	}
}