취미로 코딩하기

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

이번에 볼 문제는 백준 3340번 문제인 Multi-key Sorting이다.
문제는 아래 링크를 확인하자.

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

먼저 임의의 stable sort A와 B에 대하여 배열을 A B A 순으로 정렬하는 것과 B A 순으로 정렬하는 것이 동일함을 관찰하자.

다음은 위 관찰에 대한 정당성을 간단히 서술한 것이다: 같은 원소들로 이루어진 두 배열에 "B A"라는 순서의 정렬을 적용한 결과물이라는 관점으로 볼 때 각 정렬으로 얻는 배열 위에서 정렬기준값이 다른 두 원소는 서로 같은 상대적 위치에 있음을 알 수 있다. 또한 정렬기준값이 같은 두 원소는 처음에 A를 적용하나 안하나 상대적 위치가 변하지 않으므로(stable sort) 이 경우에도 각 정렬을으로 얻는 배열 위에서 서로 같은 상대적 위치에 있음을 알 수 있다.

따라서 주어지는 정렬의 수열에서 같은 정렬은 마지막에 주어진 정렬만 수행해도 된다는 점을 알 수 있다. 또한 모든 등장한 정렬은 적어도 한 번씩은 등장해야 함은 자명하므로, 위와 같은 성질을 갖는 정렬의 수열을 출력해 문제를 해결하자.

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

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

int C, N;
vector<int> vec, ans;
bool visited[1000001];

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

	cin >> C >> N;
	while (N--) {
		cin >> vec.emplace_back();
	}
	while (!vec.empty()) {
		if (!visited[vec.back()]) {
			visited[vec.back()] = 1;
			ans.emplace_back(vec.back());
		}
		vec.pop_back();
	}

	cout << ans.size() << '\n';
	while (!ans.empty()) {
		cout << ans.back() << ' ';
		ans.pop_back();
	}
}

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

이번에 볼 문제는 백준 2942번 문제인 퍼거슨과 사과이다.
문제는 아래 링크를 확인하자.

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

사과를 나누어줄 사람 수는 R의 약수이면서 G의 약수들과 같음을 관찰하자.

따라서 R의 모든 약수를 살펴보면서 그 중 G의 약수이기도 한 값들을 골라 문제의 답을 출력할 수 있다.

R의 모든 약수를 찾는 것은 \(O(\sqrt{R})\)에 할 수 있고 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

#include <iostream>
using namespace std;

int R, G;

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

	cin >> R >> G;
	int i = 1;
	for (; i * i < R; i++) {
		if (R % i == 0 && G % i == 0) cout << i << ' ' << R / i << ' ' << G / i << '\n';
		if (R % (R / i) == 0 && G % (R / i) == 0) cout << R / i << ' ' << R / (R / i) << ' ' << G / (R / i) << '\n';
	}
	if (i * i == R && G % i == 0) cout << i << ' ' << R / i << ' ' << G / i << '\n';
}

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

이번에 볼 문제는 백준 2852번 문제인 NBA 농구이다.
문제는 아래 링크를 확인하자.

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

새로 점수가 나는 순간마다 (1) 그 시점 직전까지 점수를 앞서나가던 팀이 존재한다면 그 팀의 점수를 앞서나가던 기간을 갱신하고 (2) 점수를 새로 갱신해나가는 것을 반복해 문제를 해결하자. 단, 마지막으로 점수가 난 다음 경기가 끝날 때까지의 시간은 위 과정에서 처리하지 않으므로 별도로 처리해주자.

문제의 답을 출력할 때 MM:SS의 출력 형식을 지켜야 함에 유의하자. 예를 들어 답으로 01:02를 출력해야 하는 경우에 1:2를 출력해 오답을 받지 않도록 유의하자.

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

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

int Q;
int team, oldT; string s;
int scr1, scr2, ans1, ans2;
int m1, s1, m2, s2;

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

	cin >> Q;
	while (Q--) {
		cin >> team >> s;
		int T = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2));
		if (scr1 > scr2) ans1 += T - oldT;
		else if (scr1 < scr2) ans2 += T - oldT;
		oldT = T;
		if (team == 1) scr1++;
		else scr2++;
	}

	if (scr1 > scr2) ans1 += 2880 - oldT;
	else if (scr1 < scr2) ans2 += 2880 - oldT;

	m1 = ans1 / 60, s1 = ans1 % 60;
	if (m1 < 10) cout << 0;
	cout << m1 << ':';
	if (s1 < 10) cout << 0;
	cout << s1 << '\n';
	m2 = ans2 / 60, s2 = ans2 % 60;
	if (m2 < 10) cout << 0;
	cout << m2 << ':';
	if (s2 < 10) cout << 0;
	cout << s2 << '\n';
}

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

이번에 볼 문제는 백준 3018번 문제인 캠프파이어이다.
문제는 아래 링크를 확인하자.

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

set 자료구조를 이용해 문제를 해결해보자.

i번 사람이 현재 알고 있는 노래를 모두 담고 있는 집합을 st[i]라 하자. 이 때, 1번을 제외한 사람들이 모였을 때에는 각 사람들이 알고 있는 노래의 집합의 합집합을 구해 각 모인 사람의 st[i]를 그 집합으로 바꿔주고, 1번을 포함한 사람들이 모였을 때에는 각 모인 사람의 아는 노래에 새 노래를 하나씩 집어넣는 것으로 문제를 해결할 수 있다. 이 과정에서 1번이 k번째로 만드는 새 노래의 이름을 k로 지으면 구현을 편리하게 할 수 있다.

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

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

int N, E;
set<int> st[101];
int num;

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

	cin >> N >> E;
	while (E--) {
		int K; cin >> K;
		vector<int> vec;
		set<int> tmp;
		bool is_bard = 0;
		while (K--) {
			int x; cin >> x;
			vec.emplace_back(x);
			if (x < 2) is_bard = 1;
		}
		if (is_bard) {
			num++;
			for (auto& x : vec) st[x].insert(num);
		}
		else {
			for (auto& x : vec) {
				for (auto& xx : st[x]) tmp.insert(xx);
			}

			for (auto& x : vec) {
				for (auto& xx : tmp) st[x].insert(xx);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (st[i].size() == num) cout << i << '\n';
	}
}

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

이번에 볼 문제는 백준 4649번 문제인 Tanning Salon이다.
문제는 아래 링크를 확인하자.

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

각 손님이 방문하는 상태인지 나가는 상태인지를 알기 위한 visited 배열을 준비해 문제를 해결하자.

특히 빈 베드가 없을 때 들어오는 손님은 기존 태닝중인 손님보다 항상 먼저 나간다는 조건이 있으므로, 새 손님이 들어올 때 현재 가게에 있는 손님 수가 베드보다 많은지를 확인하는 것으로 문제의 답을 간단하게 구할 수 있다.

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

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

int bed; string s;
int cnt, ans;
bool visited[128];

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

	while (cin >> bed >> s) {
		ans = 0;
		for (auto& l : s) {
			if (visited[l]) visited[l] = 0, cnt--;
			else {
				visited[l] = 1, cnt++;
				if (cnt > bed) ans++;
			}
		}

		if (ans) cout << ans << " customer(s) walked away.\n";
		else cout << "All customers tanned successfully.\n";
	}
}

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

이번에 볼 문제는 백준 4335번 문제인 숫자 맞추기이다.
문제는 아래 링크를 확인하자.

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

한 게임에서 주어지는 조건들을 종합하면 다음과 같다.

(1) 찾고자 하는 수는 \(x_1, x_2, ..., x_k\)보다 작아야 한다.

(2) 찾고자 하는 수는 \(y_1, y_2, ..., y_k\)커야 한다.

(1)은 \(x_i\)중 가장 작은 값을 저장해두는 것으로, (2)는 \(y_i\) 중 가장 큰 값을 저장해두는 것으로 간단하게 확인할 수 있다. 이를 이용해 각 게임마다 스탠이 거짓말을 했는지 알아내자.

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

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

int L = 0, R = 11;
int x; string s;

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

	while (cin >> x >> s >> s) {
		if (s[0] == 'h') R = min(R, x);
		else if (s[0] == 'l') L = max(L, x);
		else {
			if (L < x && x < R) cout << "Stan may be honest\n";
			else cout << "Stan is dishonest\n";
			L = 0, R = 11;
		}
	}
}