취미로 코딩하기

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

이번에 볼 문제는 백준 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();
	}
}

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

이번에 볼 문제는 백준 6844번 문제인 Keep on Truckin'이다.
문제는 아래 링크를 확인하자.

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

각 모텔에 도달할 수 있는 경우의 수는 해당 모텔에서 음의 방향으로 폐구간 [A,B]에 속한 수만큼 떨어진 각 모텔들까지 도달할 수 있는 경우의 수의 합과 같음을 관찰하자.

위의 관찰을 이용하면 문제를 해결하는 DP 알고리즘을 간단히 고안해낼 수 있다. 이를 구현해주자.

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

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

int A, B, N;
int motel[14001];
ll dp[14001];

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

	dp[0] = 1;
	motel[0] = motel[990] = motel[1010] = motel[1970] = motel[2030] = motel[2940] = motel[3060] = motel[3930] = motel[4060] = motel[4970] = motel[5030] = motel[5990] = motel[6010] = motel[7000] = 1;

	cin >> A >> B >> N;
	while (N--) {
		int x; cin >> x;
		motel[x] = 1;
	}

	for (int i = 0; i < 7000; i++) {
		if (!motel[i]) continue;
		for (int k = A; k <= B; k++) {
			dp[i + k] += dp[i];
		}
	}

	cout << dp[7000];
}

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

이번에 볼 문제는 백준 6842번 문제인 Deal or No Deal Calculator이다.
문제는 아래 링크를 확인하자.

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

문제의 요구에 따라 (남은 briefcase에 든 돈의 총합) / (남은 briefcase의 개수) 과 (deal로 제안된 값)의 대소 비교에 따라 "deal" 또는 "no deal"을 출력하는 프로그램을 작성하자.

부동 소수점 오차가 걱정되는 경우, 남은 briefcase의 개수는 항상 양의 정수이므로 위 대소 비교 결과는 (남은 briefcase에 든 돈의 총합)과 (deal로 제안된 값) * (남은 briefcase의 개수)의 대소 비교 결과와 같음을 이용하는 것으로 실수 연산을 피할 수 있다.

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

#include <iostream>
using namespace std;

int N, cnt, total = 1691600, deal;
int val[11] = { 0,100,500,1000,5000,10000,25000,50000,100000,500000,1000000 };

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

	cin >> N; cnt = 10 - N;
	while (N--) {
		int x; cin >> x;
		total -= val[x];
	}

	cin >> deal;
	if (deal * cnt > total) cout << "deal";
	else cout << "no deal";
}