취미로 코딩하기

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

이번에 볼 문제는 백준 32980번 문제인 분리배출이다.
문제는 아래 링크를 확인하자.

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

어떤 쓰레기가 한 가지 품목만으로 구성되어 있다면 이 쓰레기는 해당 품목으로 버리거나 일반 쓰레기로 버릴 수 있으며, 그렇지 않은 경우 항상 일반 쓰레기로만 버릴 수 있음을 관찰하자. 특히, 몇몇 일상적인 생각과는 다르게 문제 조건만을 따지면 한 가지 품목만으로 이루어진 쓰레기도 일반 쓰레기로 버려도 된다는 점에 유의하자. 이 경우 두 비용 중 더 저렴한 비용으로 쓰레기를 처리하면 된다. 문제 조건상 일반 쓰레기로 버리는 비용이 재활용 쓰레기로 버리는 비용보다 저렴할 수도 있다는 점에도 유의하자.

어떤 쓰레기가 단일 품목으로 이루어져있는지 여부는 각 인접한 두 문자에 대하여 서로 다른 문자의 쌍이 존재하는지 확인하는 것으로 단순하게 구현할 수 있다.

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

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

ll N, ans;
ll cst[128];
ll cnt[128], tmp[128];
string s;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		memset(tmp, 0, sizeof(tmp));
		cin >> s;
		for (auto &l:s) tmp[l]++;
		if (tmp[s.front()] == s.length()) cnt[s.front()] += s.length();
		else cnt['O'] += s.length();
	}
	cin >> cst['P'] >> cst['C'] >> cst['V'] >> cst['S'] >> cst['G'] >> cst['F'] >> cst['O'];
	for (int i = 0; i < 128; i++) ans += min(cst[i], cst['O']) * cnt[i];
	cout << ans;
}

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

이번에 볼 문제는 백준 32978번 문제인 아 맞다 마늘이다.
문제는 아래 링크를 확인하자.

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

앞서 등장한 \(N\)가지 재료 중, 뒤에 주어진 \(N-1\)개의 재료 목록에서 빠진 재료를 찾는 문제이다.

재료의 수가 충분히 많으므로 각 앞서 주어진 재료마다 뒤에 주어진 재료 목록에 그 재료가 있는지 확인하는 것으로 문제를 충분히 해결할 수 있다.

다른 방법으로 set 자료구조에 \(N\)가지 재료를 모두 저장한 다음 \(N-1\)개의 재료를 set에서 제거하여 남는 재료를 찾을 수도 있다.

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

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

int N;
set<string> st;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		st.insert(s);
	}
	for (int i = 1; i < N; i++) {
		string s; cin >> s;
		st.erase(s);
	}
	cout << *st.begin();
}

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

이번에 볼 문제는 백준 33042번 문제인 이변마작 1이다.
문제는 아래 링크를 확인하자.

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

패가 주어질 때마다 그 패가 5번째 등장하는지 판단하자. 만약 그 패가 5번째 등장하는 패라면 주어진 순서를 답으로 출력하고 알고리즘을 종료하는 것으로 문제가 해결된다. 모든 패를 확인한 뒤에도 5번 등장한 패가 없다면 답은 0이 된다.

각 패의 개수를 세는 것은 map을 이용해 간단하게 구현할 수 있다. \(N\)의 크기가 작으므로 주어진 문자열을 배열에 모두 저장하고 패가 들어올 때마다 앞서 등장한 문자열 중 같은 문자열이 몇 개 있는지 직접 세는 방식으로도 문제를 충분히 빠르게 해결할 수 있다.

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

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

int N;
map<string, int> mp;

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

	cin >> N;
	for (int n = 1; n <= N ; n++) {
		string s; cin >> s;
		mp[s]++;
		if (mp[s] == 5) {
			cout << n;
			return 0;
		}
	}
	cout << 0;
}

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

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

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

주어진 문자열을 둘로 나눌 수 있는 지점에서 모두 나눠보면서 그 두 문자열의 L과 O의 개수가 서로 다른지를 매번 확인해주자. \(N\)이 매우 작으므로 이와 같은 구현으로도 충분히 문제를 해결할 수 있다.

물론 전체 L과 O의 개수 및 각 접두사의 L과 O의 개수를 관리해 문제를 더 효율적으로 해결할 수도 있다. 아래의 구현은 이 풀이를 바탕으로 한다.

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

#include <iostream>
using namespace std;

int N, cntL, cntO, cntLL, cntOO;
string s;

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

	cin >> N >> s;
	for (auto &l:s) {
		if (l == 'L') cntL++;
		else cntO++;
	}
	for (int i = 0; i + 1 < N; i++) {
		if (s[i] == 'L') cntLL++;
		else cntOO++;
		if (cntLL != cntL - cntLL && cntOO != cntO - cntOO) {
			cout << i + 1;
			return 0;
		}
	}
	cout << -1;
}

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

이번에 볼 문제는 백준 2415번 문제인 직사각형이다.
문제는 아래 링크를 확인하자.

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

어떤 (일치하지 않는) 두 선분이 직사각형의 마주보는 두 변일 필요충분조건 중 하나는 (1) 두 선분의 기울기가 같고 (2) 두 선분의 길이가 같고 (3) 두 선분의 양 끝점을 (교차하지 않게) 이어 얻을 수 있는 다른 두 선분이 기존 두 선분과 수직해야한다는 것이다. 따라서 위의 세 조건을 만족하게끔 모든 가능한 선분을 분류할 수 있다면 그 선분들 중 서로 가장 멀리 떨어진 두 선분으로 이루어진 직사각형을 모두 조사하는 것으로 문제를 해결할 수 있을 것이다.

어떤 선분이 잇는 두 점이 \((x_1,y_1)\)과 \((x_2,y_2)\)라 하자. 먼저 (1)과 (2)는 각 선분에 대하여 \(x_2-x_1\)과 \(y_2-y_1\)이 서로 같거나 두 값 모두 부호가 다를 경우 성립하며, 이는 필요충분조건이 된다. (3)은 원점을 지나며 주어진 선분과 수직한 다른 직선과 선분의 양끝점 사이의 부호 있는 거리(?)를 이용해 저장할 수 있다. 이는 점과 직선 사이의 거리 공식에 절댓값을 씌우지 않는 것으로 어렵지 않게 계산할 수 있으며, 이 때 분모는 (1)과 (2)를 저장하기 위한 값에 종속적이므로 이를 생략하여 저장하면 이 값 또한 정수로 관리할 수 있다. 이 세 값이 동일한 두 선분을 구성하는 네 점은 직사각형을 항상 구성할 수 있으므로, 이 3-tuple을 관리하는 것으로 문제를 해결할 수 있다.

위의 값이 같은 선분들에 대하여 이 선분과 평행하면서 원점을 지나는 직선 사이의 (부호 있는) 거리(?)의 최댓값과 최솟값을 관리하여 문제를 해결하자. 점과 직선 사이의 거리 공식의 분모에 들어가는 값이 선분의 길이와 같으므로, 분자만 저장해 나중에 분자의 최댓값에서 최솟값을 빼기만 하는 것으로 직사각형의 넓이를 얻을 수 있다!

위에서 "부호 있는 거리(?)"라고 언급한 값은 실제로는 방향이 있는 값이므로 거리는 아니지만 직관적인 설명을 위해 이렇게 서술하였다.

이와 같이 풀이하면 map을 쓰면서 대충 구현해도 예전 메모리제한(64MB)보다 적은 메모리를 사용해 문제를 해결할 수 있다.

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

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

int N;
int P[1500][2];
ll ans;
map<pair<pair<ll, ll>, ll>, pair<ll, ll>> mp;

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ll dx = P[i][0] - P[j][0], dy = P[i][1] - P[j][1];
            if (!dx || dx * dy < 0) continue;
            dx = abs(dx), dy = abs(dy);
            ll D = min(dx * P[i][0] + dy * P[i][1], dx * P[j][0] + dy * P[j][1]), DD = dy * P[i][0] - dx * P[i][1];
            auto p = make_pair(make_pair(dx, dy), D);
            if (mp.count(p)) {
                auto &pp = mp[p];
                pp.first = max(pp.first, DD), pp.second = min(pp.second, DD);
            }
            else mp[p] = make_pair(DD, DD);
        }
    }

    for (auto &p:mp) ans = max(ans, p.second.first - p.second.second);
    cout << ans;
}

여담)

문제를 해결하고 나서 다른 사람들의 풀이를 보니 대체로 직사각형의 두 대각선은 중점과 길이는 같다는 성질을 이용해 중점과 길이가 같은 대각선 후보를 모으고 두 대각선을 골라 만들 수 있는 직사각형을 모두 조사하는 방식을 사용하고 있었다. 이와 같이 풀이하기 위해서는 중점과 길이가 같고 양끝점이 모두 정수 격자점인 선분이 많이 존재하지 않는다는 추가적인 관찰을 하거나 각도를 기준으로 하는 슬라이딩 윈도우를 적용하는 등의 추가적인 작업이 필요하다. 이와 같은 풀이의 아이디어나 구현, 그리고 최적화 등은 쉽지 않지만 알아둘 가치가 있는 풀이라고 생각해 같이 기록해 둔다.

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

이번에 볼 문제는 백준 27947번 문제인 가지 밭 게임이다.
문제는 아래 링크를 확인하자.

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

새로운 말뚝을 하나 추가하면 가장 큰 다각형의 넓이는 커지거나 그대로일 수는 있지만 작아질 수는 없다는 점을 관찰하자. 기존 말뚝으로 만들 수 있는 다각형을 여전히 다 만들 수 있기 때문이다.

따라서 게임이 진행되면 만들어질 수 있는 가장 큰 다각형의 넓이는 단조증가하므로 게임이 몇 번째 차례까지 진행되어야 최대 넓이가 \(A\) 이상이 되는지는 이분탐색으로 구할 수 있다.

주어지는 점을 꼭짓점으로 하여 구성할 수 있는 가장 넓이가 큰 다각형은 주어진 점의 볼록 껍질(convex hull)과 같으므로 볼록 껍질을 구하는 다양한 알고리즘(글쓴이는 Andrew's algorithm을 구현하였다.)과 다각형의 넓이를 구하는 식인 사선 공식(shoelace formula)을 활용해 어렵지 않게 구현할 수 있다.

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

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

ll CCW(pll &p1, pll &p2, pll &p3) {
    return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - p1.first * p3.second - p2.first * p1.second - p3.first * p2.second;
}

ll N, A, L, R;
vector<pair<pll, int>> P;
vector<pll> uhull, lhull;

ll func(ll K) {
    uhull.clear(), lhull.clear();
    for (auto &p:P) {
        if (p.second > K) continue;
        while (uhull.size() > 1 && CCW(uhull[uhull.size() - 2], uhull.back(), p.first) >= 0) uhull.pop_back();
        uhull.emplace_back(p.first);
    }
    for (auto &p:P) {
        if (p.second > K) continue;
        while (lhull.size() > 1 && CCW(lhull[lhull.size() - 2], lhull.back(), p.first) <= 0) lhull.pop_back();
        lhull.emplace_back(p.first);
    }
    lhull.pop_back();
    while (!lhull.empty()) {
        uhull.emplace_back(lhull.back());
        lhull.pop_back();
    }
    ll usize = uhull.size(), ret = 0;
    for (int i = 0; i + 1 < usize; i++) ret += uhull[i].first * uhull[i + 1].second - uhull[i].second * uhull[i + 1].first;
    return abs(ret);
}

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

    cin >> N >> A; A *= 2;
    P.reserve(N + 3);
    uhull.reserve(N + 4), lhull.reserve(N + 4);
    for (int i = -2; i <= N; i++) {
        ll x, y; cin >> x >> y;
        P.emplace_back(make_pair(make_pair(x, y), i));
    }
    
    sort(P.begin(), P.end());
    if (func(N) < A) {
        cout << "draw";
        return 0;
    }
    
    L = 1, R = N;
    while (L < R) {
        ll mid = (L + R) / 2;
        if (func(mid) >= A) R = mid;
        else L = mid + 1;
    }
    
    if (L & 1) cout << "wapas";
    else cout << "wider";
}