취미로 코딩하기

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

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

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

이번에 볼 문제는 백준 14476번 문제인 최대공약수 하나 빼기이다.
문제는 아래 링크를 확인하자.

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

최대공약수는 유클리드 호제법으로 빠르게 구할 수 있다.

어떤 한 수를 제외한 다른 모든 수의 최대공약수는 그 수의 왼쪽에 있는 모든 수의 최대공약수와 오른쪽에 있는 모든 수의 최대공약수와 같음을 관찰하자. 따라서 왼쪽부터의 \(i\)번째 수까지의 최대공약수를 계산해 둔 배열과 오른쪽부터 \(i\)번째 수까지의 최대공약수를 계산해 둔 배열을 각각 \(O(N\lg N)\)에 구해두면 \(i\)번째 수를 제외한 수의 최대공약수를 각각 \(\lg N\)에 계산할 수 있게 된다.

각 수에 대하여 그 수를 제외한 나머지 수의 최대공약수를 계산하고, 그 중 문제의 조건을 만족하는 최대공약수수의 최댓값과 그 때의 인덱스를 저장해 문제를 해결하자.

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

#include <iostream>
using namespace std;

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

int N, ans = -1, aidx;
int A[1000002], L[1000002], R[1000002];

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

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) L[i] = gcd(L[i - 1], A[i]);
    for (int i = N; i > 0; i--) R[i] = gcd(R[i + 1], A[i]);
    for (int i = 1; i <= N; i++) {
        int val = gcd(L[i - 1], R[i + 1]);
        if (A[i] % val) {
            if (ans < val) ans = val, aidx = i;
        }
    }
    if (ans < 0) cout << ans;
    else cout << ans << ' ' << A[aidx];
}

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

이번에 볼 문제는 백준 1451번 문제인 직사각형으로 나누기이다.
문제는 아래 링크를 확인하자.

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

어떤 직사각형을 두 개의 직사각형으로 나누는 방법은 가로방향이나 세로방향으로 한 번 자르는 것 외에는 없다. 그리고 세 개의 직사각형으로 나누는 방법은 (1)가로 방향이나 세로 방향으로 두 번 자르거나 (2) 가로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 세로로 한 번 자르거나 (3) 세로 방향으로 한 번 자르고 그 결과로 나온 직사각형 중 하나를 가로로 한 번 자르는, 총 세 가지 외에는 없다.

위의 관찰을 이용하여 자를 수 있는 모든 방법에 대하여 직사각형의 합의 곱을 계산해 그 중 최댓값을 구하자. 2차원 누적 합 배열을 이용하면 위의 계산을 효율적으로 할 수 있을 것이다.

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

int R, C; ll ans;
ll A[51][51];

ll func(int r1, int c1, int r2, int c2) {
    return A[r2][c2] - A[r1 - 1][c2] - A[r2][c1 - 1] + A[r1 - 1][c1 - 1];
}

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

    cin >> R >> C;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            char x; cin >> x;
            A[r][c] += x - '0';
            A[r][c] += A[r - 1][c] + A[r][c - 1] - A[r - 1][c - 1];
        }
    }
    for (int r1 = 1; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            ans = max(ans, func(1, 1, r1, C) * func(r1 + 1, 1, r2, C) * func(r2 + 1, 1, R, C));
        }
    }
    for (int c1 = 1; c1 < C; c1++) {
        for (int c2 = c1 + 1; c2 < C; c2++) {
            ans = max(ans, func(1, 1, R, c1) * func(1, c1 + 1, R, c2) * func(1, c2 + 1, R, C));
        }
    }

    for (int r = 1; r < R; r++) {
        for (int c = 1; c < C; c++) {
            ans = max(ans, func(1, 1, r, c) * func(1, c + 1, r, C) * func(r + 1, 1, R, C));
            ans = max(ans, func(1, 1, r, C) * func(r + 1, 1, R, c) * func(r + 1, c + 1, R, C));
        }
    }
    for (int c = 1; c < C; c++) {
        for (int r = 1; r < R; r++) {
            ans = max(ans, func(1, 1, r, c) * func(r + 1, 1, R, c) * func(1, c + 1, R, C));
            ans = max(ans, func(1, 1, R, c) * func(1, c + 1, r, C) * func(r + 1, c + 1, R, C));
        }
    }
    cout << ans;
}

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

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

이번에 볼 문제는 백준 32963번 문제인 맛있는 사과이다.
문제는 아래 링크를 확인하자.

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

먼저 사과의 나열 순서와 답은 상관관계가 없으므로 주어진 사과를 크기순으로 정렬해도 답이 변하지 않음을 관찰하자. 그리고 사과를 크기순으로 정렬하자.

다음으로, 큰 사과부터 차례대로 보면서 가장 큰 사과의 크기가 얼마인지, 그 크기의 사과가 몇개인지를 두 변수를 활용해 관리하고, 크기 역순으로 해당 사과까지 확인했을 때의 문제의 답이 무엇인지를 잘 기록해두자.

이제 각 쿼리로 주어진 수에 대하여 해당 수보다 크거나 같은 사과 중 가장 인덱스가 작은 사과부터 마지막 사과까지의 사과 중 가장 큰 사과의 개수가 몇 개인지 앞서 구한 배열을 이용해 답하는 것으로 문제를 해결할 수 있다. 이러한 인덱스는 이진 탐색으로 구할 수 있다.

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

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

int N, Q, mx = -1, cnt = 0;
pair<int, int> P[200000];

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

    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> P[i].first;
    for (int i = 0; i < N; i++) cin >> P[i].second;

    sort(P, P + N);
    for (int i = N - 1; i > -1; i--) {
        if (P[i].second > mx) mx = P[i].second, cnt = 1;
        else if (P[i].second == mx) cnt++;
        P[i].second = cnt;
    }

    while (Q--) {
        int K, L = 0, R = N - 1; cin >> K;
        if (P[N - 1].first < K) cout << 0 << '\n';
        else {
            while (L < R) {
                int mid = (L + R) / 2;
                if (P[mid].first < K) L = mid + 1;
                else R = mid;
            }
            cout << P[L].second << '\n';
        }
    }
}

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

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

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

문제에 주어진 대로, 먼저 주어지는 수 중 가장 큰 값과 작은 값을 구하자. 그리고 큰 값의 절반에서 작은 값을 뺀 값이 양수이면 그 값이, 양수가 아니라면 0이 문제의 답이 된다.

조건에 따라 입력으로 주어지는 \(P\) 값은 모두 10의 배수이므로 2로 나눈 값이 소수가 되는 경우는 입력으로 주어지지 않음을 확인하자. 따라서 별다른 걱정 없이 정수로 모든 구현을 마쳐도 된다.

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

#include <iostream>
using namespace std;

int N, mn = 1000000007, mx = -1000000007;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		mn = min(mn, x);
		mx = max(mx, x);
	}

	cout << max(mn - mx / 2, 0);
}

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

이번에 볼 문제는 백준 32936번 문제인 타임머신이다.
문제는 아래 링크를 확인하자.

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

답이 "-inf"가 되려면 일단 (1) 1번 정점에서 타임머신을 이용하러 갈 수 있으며 (2) 타임머신 이용 후 다시 타임머신을 이용하러 갈 수 있고 (3) 2의 과정에 드는 시간이 타임머신으로 되돌아가는 시간보다 적으며 (4) 타임머신 이용 후 \(N\)번 정점으로 이동할 수 있어야 한다.

위의 내용이 성립하지 않으면 일단 답은 "-inf'가 아니다. 이 때 가능한 답의 후보는 (1)1번 정점에서 타임머신을 이용하지 않고 \(N\)번 정점으로 가는 것과 (2) 1번 정점에서 타임머신을 한 번 이용하고 \(N\)번 정점으로 가는 것이다. 타임머신을 2번 이상 사용하는 것이 1번 사용한 것보다 더 거리가 짧다면 타임머신을 더 많이 사용하는 것이 이득이 됨을 관찰하자.

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

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

int N, M, A, B, C;
vector<int> G[200001];
queue<int> que;
int dist[200001];
int dd = 1000000007, da = 1000000007, db = 1000000007, dba = 1000000007;

void bfs(int S) {
	memset(dist, 0, sizeof(dist));
	dist[S] = 1;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto &nxt:G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

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

	cin >> N >> M >> A >> B >> C;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	bfs(1);
	if (dist[N]) dd = dist[N] - 1;
	if (dist[A]) da = dist[A] - 1;
	bfs(B);
	if (dist[N]) db = dist[N] - 1;
	if (dist[A]) dba = dist[A] - 1;

	if (da < 1000000007 && db < 1000000007) dd = min(dd, da + db - C);
	if (da < 1000000007 && db < 1000000007 && dba < 1000000007 && dba < C) cout << "-inf";
	else if (dd < 1000000007) cout << dd;
	else cout << 'x';
}