취미로 코딩하기

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

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

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

이번에 볼 문제는 백준 32941번 문제인 왜 맘대로 예약하냐고이다.
문제는 아래 링크를 확인하자.

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

각 조원에 대하여 참석 가능한 교시 중 \(X\)교시가 있는지 확인하자. 만약 \(X\)교시에 참석이 불가능한 조원이 한 명이라도 있으면 답은 "NO"가 되고, 그렇지 않다면 답은 "YES"가 된다.

위 내용의 구현은 반복문과 조건문을 적절히 활용하는 것으로 해낼 수 있다.

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

#include <iostream>
using namespace std;

int T, X, N, K;

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

    cin >> T >> X >> N;
    while (N--) {
        bool chk = 0;
        cin >> K;
        while (K--) {
            int x; cin >> x;
            if (x == X) chk = 1;
        }
        if (!chk) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
}

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

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

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

한 과목당 같은 학번은 단 한 번씩 주어지므로, 등장하는 학번이 각각 몇 번씩 나오는 지 세는 것으로 문제를 충분히 해결할 수 있다.

등장하는 학번의 개수를 세는 것은 크기 2천만인 배열을 이용하거나 map을 이용하는 등 여러 방법으로 구현할 수 있다.

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

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

int N, M, x, K, ans;
map<int, char> mp;

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

    cin >> N >> K;
    while (N--) {
        cin >> M;
        while (M--) {
            cin >> x; mp[x]++;
        }
    }
    for (auto &p:mp) {
        if (p.second >= K) ans++;
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 11643번 문제인 The Magical 3이다.
문제는 아래 링크를 확인하자.

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

어떤 양의 정수 \(n\)의 \(b\)진법으로 나타냈을 때의 일의 자리가 3이라는 것은 \(3<b\)이며 \(n\)을 \(b\)로 나누었을 때의 나머지가 \(k\)와 같다는 것과 동치이다. 따라서 \(n-3\)은 음이 아닌 \(b\)의 배수여야 한다.

위의 관찰을 이용하면 답의 후보로 살펴야 하는 수는 \(n-3\)의 약수 뿐임을 알 수 있다. \(n-3\)의 모든 약수에 한 번씩 접근하여 가능한 답의 최솟값을 구해 문제를 해결하자. 이는 테스트케이스 당 시간복잡도 \(O(\sqrt{n})\)에 수행할 수 있다.

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

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

ll N;

void solve() {
    if (N < 3) {
        cout << "No such base\n";
        return;
    }
    else if (N == 3) {
        cout << 4 << '\n';
        return;
    }
    N -= 3;
    ll ans = 1000000000000000007LL;
    for (ll k = 1; k * k <= N; k++) {
        if (N % k) continue;
        if (k > 3) ans = min(ans, k);
        if (N / k > 3) ans = min(ans, N / k);
    }
    if (ans < 1000000000000000007LL) cout << ans << '\n';
    else cout << "No such base\n";
}

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

    cin >> N;
    while (N) {
        solve();
        cin >> N;
    }
}

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

이번에 볼 문제는 백준 1800번 문제인 인터넷 설치이다.
문제는 아래 링크를 확인하자.

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

문제를 다른 시각으로 해석해보자. 1번 컴퓨터와 \(N\)번 컴퓨터를 이을 수 있다는 전제 하에, 주어진 문제는 "어떤 \(x\)에 대하여 비용 \(x\)를 넘는 에지를 \(K\)개 이하로 사용해 1번 컴퓨터와 \(N\)번 컴퓨터 사이를 이을 수 있는 최소 \(x\)는 무엇인지"를 찾는 문제로 생각할 수 있다. 어떤 \(x\)값에 대하여 두 컴퓨터를 이을 수 있다면 그보다 큰 \(x\)값이 주어져도 두 컴퓨터를 이을 수 있으며 두 컴퓨터를 이을 수 없다면 그보다 작은 \(x\)값이 주어져도 두 컴퓨터를 이을 수 없으므로, \(x\)의 값은 이진탐색을 이용해 계산할 수 있다.

두 컴퓨터가 이어질 수 있는지를 생각해야 한다는 점을 잊지 말자.

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

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

int N, E, K;
vector<pair<int, int>> G[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int dist[1001];
bool dijkstra(int mid) {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int cur = pq.top().second, d = pq.top().first; pq.pop();
        if (dist[cur] < d) continue;
        for (auto &p:G[cur]) {
            int nxt = p.first, dd = d;
            if (p.second > mid) dd++;
            if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
        }
    }
    return (dist[N] <= K);
}

int L, R = 1000001;

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

    cin >> N >> E >> K;
    while (E--) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }

    while (L < R) {
        int mid = (L + R) / 2;
        if (dijkstra(mid)) R = mid;
        else L = mid + 1;
    }
    if (L == 1000001) cout << -1;
    else cout << L;
}