취미로 코딩하기

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

이번에 볼 문제는 백준 26596번 문제인 황금 칵테일이다.
문제는 아래 링크를 확인하자.

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

칵테일에 들어간 서로 다른 두 재료의 비율이 문제의 조건을 만족하는 경우가 있는지를 확인하는 문제이다.

가능한 재료의 종류는 최대 \(M\)가지로 충분히 적다. 따라서 가능한 모든 재료 쌍을 직접 살펴 비율이 조건을 만족하는지 확인하는 \(O(M^2)\) 브루트포스로 문제를 충분히 해결할 수 있다.

같은 재료를 여러 번 섞었을 수 있으므로 각 재료의 양을 map을 이용해 관리해주자.

\(\lfloor a_i*1.618\rfloor\)의 계산은 단순히 \(a_i\)에 1618을 곱한 뒤 1000으로 나눈 몫을 계산하는 것으로 실수연산 없이 해낼 수 있으니 참고하자.

같은 두 재료의 비율을 계산하지 않도록 유의하자. 예를 들어 어떤 재료의 양이 1이고 나머지 재료의 양이 1이 아닐 때 해당 재료를 두 재료로 생각해 판단하는 일이 발생하지 않도록 유의하자. 물론 서로 다른 재료의 양이 각각 1인 경우는 고려해주어야 한다.

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

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

int N;
map<string, int> mp;
vector<int> vec;

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

	cin >> N;
	while (N--) {
		string s; int x; cin >> s >> x;
		if (mp.count(s)) mp[s] += x;
		else mp.insert(make_pair(s, x));
	}

	for (auto &p : mp) vec.emplace_back(p.second);
	int N = vec.size();
	for (int i = 0; i < N; i++) {
		int xx = vec[i] * 1618 / 1000;
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			int y = vec[j];
			if (xx == y) {
				cout << "Delicious!";
				return 0;
			}
		}
	}

	cout << "Not Delicious...";
}

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

이번에 볼 문제는 백준 28446번 문제인 볼링공 찾아주기이다.
문제는 아래 링크를 확인하자.

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

볼링공의 무게를 key로 갖는 map을 활용하면 문제를 간단히 해결할 수 있다.

map을 이용하지 않더라도 offline query 기법을 이용해 문제를 해결할 수도 있다. 구체적으로, 쿼리를 모두 읽어 각 1번 쿼리로부터 알 수 있는 최종적으로 보관중인 모든 볼링공을 무게순으로 먼저 정렬한 다음 각 2번 쿼리에 대한 답을 이진 탐색을 이용해 구해 문제를 해결할 수도 있다.

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

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

int Q;
map<int, int> mp;

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

	cin >> Q;
	while (Q--) {
		int q; cin >> q;
		if (q == 1) {
			int x, w; cin >> x >> w;
			mp.insert(make_pair(w, x));
		}
		else {
			int w; cin >> w;
			cout << mp[w] << '\n';
		}
	}
}

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

이번에 볼 문제는 백준 26267번 문제인 은?행 털!자 1이다.
문제는 아래 링크를 확인하자.

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

좌표 \(X\)에 있는 은행에 시간 \(T\)에 방문하려면 시우는 좌표 \(X-T\)에서 움직임을 시작해야 함을 관찰하자. 이 관찰을 이용하면 시우가 좌표 \(x\)에서 움직임을 시작한다면 \(X-T=x\)가 성립하는 모든 은행들을 방문할 수 있음을 알 수 있다.

모든 가능한 시작 좌표에 대하여 탐색하기에는 필요한 탐색 범위가 넓으므로, "시우가 은행을 방문할 수 있는 각 시작 좌표"에 대하여 방문할 수 있는 모든 은행을 map 등의 자료구조를 활용해 모아서 문제를 해결하자.

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

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

int N;
map<ll, ll> mp;
ll ans;

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

	cin >> N;
	while (N--) {
		ll X, T, C; cin >> X >> T >> C;
		X -= T;
		if (mp.count(X)) mp[X] += C;
		else mp.insert(make_pair(X, C));
	}

	for (auto &p : mp) {
		ans = max(ans, p.second);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 20157번 문제인 화살을 쏘자!이다.
문제는 아래 링크를 확인하자.

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

어떤 한 화살에 두 풍선이 같이 터진다면 원점과 각 풍선을 잇는 두 직선이 동일한 직선이 된다는 성질을 관찰하자. 역은 성립하지 않는데, 화살의 움직임은 직선이 아닌 반직선과 같기 때문이다. 즉 원점을 기준으로 정반대에 있는 두 풍선은 한 화살로 터트릴 수 없다.

위의 관찰을 이용하면, 한 화살로 터트릴 수 있는 모든 풍선을 찾는 것은 각 점과 원점을 잇는 직선의 기울기가 같은 점들을 모아 비교하는 것으로 할 수 있다는 것을 발견할 수 있다. 특히, 주어진 각 풍선의 \(x\) 및 \(y\)좌표를 각각 둘의 최대공약수로 나눠 얻을 수 있는 각 좌표의 개수를 센다면 원점을 기준으로 정반대에 있는 점도 자연스럽게 구분해 셀 수 있어 구현을 편하게 할 수 있다.

구현 방법에 따라 기울기가 0인(\(x\)축과 평행한) 경우와 무한대인(\(y\)축과 평행한) 직선에 유의해야 할 수도 있으니 참고하자.

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

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

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int N;
pair<int, int> P[100000];
int cntinf, cntninf;

pair<int, int> old; int combo;
int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P[i].first >> P[i].second;
		if (!P[i].first) {
			if (P[i].second > 0) cntinf++;
			else cntninf++;
			i--, N--;
		}
		else {
			int g = gcd(abs(P[i].first), abs(P[i].second));
			P[i].first /= g, P[i].second /= g;
		}
	}

	sort(P, P + N);
	for (int i = 0; i < N; i++) {
		if (old == P[i]) combo++;
		else {
			ans = max(ans, combo);
			old = P[i], combo = 1;
		}
	}
	ans = max(ans, combo);

	cout << max(ans, max(cntinf, cntninf));
}

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

이번에 볼 문제는 백준 14670번 문제인 병약한 영정이다.
문제는 아래 링크를 확인하자.

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

약의 효능(정수)에 대응되는 약의 번호(정수)를 저장한 배열을 만들어 문제를 해결하자. 약의 효능과 번호는 0 이상 100 이하의 정수로 나타내므로 이와 같은 배열을 만드는 것은 항상 가능하다.

주어지는 모든 증상에 대응되는 약이 있을 때만 출력해야 하므로, 글쓴이는 각 증상에 대응되는 약의 번호를 저장하는 벡터 및 모든 증상에 대응되는 약이 있는지를 확인하기 위한 변수를 활용해 문제를 해결했다.

약의 효능과 번호의 값이 각각 0이 될 수 있다는 점에 유의하자. 특히 배열의 값이 0으로 초기화되어 있다면 약의 번호가 0인 상황과 대응되는 약이 없는 상황을 구분할 수 없어 문제를 해결할 수 없을 것이다.

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

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

int N, Q;
int A[101];
vector<int> ans;

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

	memset(A, 0xff, sizeof(A));

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		A[x] = y;
	}
	cin >> N;
	while (N--) {
		bool chk = 1;
		ans.clear();
		cin >> Q;
		while (Q--) {
			int x; cin >> x;
			if (A[x] < 0) chk = 0;
			else ans.emplace_back(A[x]);
		}
		if (chk) {
			for (auto &x : ans) cout << x << ' ';
			cout << '\n';
		}
		else cout << "YOU DIED\n";
	}
}

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

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

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

민호가 설계한 CPU의 16-bit 단위 명령어의 구조를 따라 어셈블리어를 기계어로 번역하는 프로그램을 작성하는 문제이다.

opcode, rD, rA, rB의 값을 각각 대응되는 기계어로 출력해 문제를 해결하자. 각 값을 대응되는 값으로 바꾸는 작업은 map 등으로 간편하게 할 수 있다.

각 opcode가 'C'로 끝나는지를 따로 저장해 구현을 더 간소화할 수도 있다.

사용하지 않는 비트(5번 비트) 등을 빼먹고 구현하지 않도록 주의하자.

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

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

int T;
map<string, string> mp;
string s; int rD, rA, X, isC;
string BIT3[8] = { "000", "001", "010", "011", "100", "101", "110", "111" };
string BIT4[16] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" };

void solve() {
	cin >> s >> rD >> rA >> X;
	if (s.back() == 'C') isC = 1, s.pop_back();
	else isC = 0;

	cout << mp[s] << isC << '0' << BIT3[rD] << BIT3[rA];
	if (isC) cout << BIT4[X] << '\n';
	else cout << BIT3[X] << '0' << '\n';
}

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

	mp.insert(make_pair("ADD", "0000"));
	mp.insert(make_pair("SUB", "0001"));
	mp.insert(make_pair("MOV", "0010"));
	mp.insert(make_pair("AND", "0011"));
	mp.insert(make_pair("OR", "0100"));
	mp.insert(make_pair("NOT", "0101"));
	mp.insert(make_pair("MULT", "0110"));
	mp.insert(make_pair("LSFTL", "0111"));
	mp.insert(make_pair("LSFTR", "1000"));
	mp.insert(make_pair("ASFTR", "1001"));
	mp.insert(make_pair("RL", "1010"));
	mp.insert(make_pair("RR", "1011"));

	cin >> T;
	while (T--) solve();
}