취미로 코딩하기

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

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

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

문제의 주어진 상황은 (도착지점, 사용해야 하는 비용)의 쌍을 하나의 정점으로, 서로 이동할 수 있는 관계의 두 지점에 대하여 이동비용만큼 영향을 주는 관계(단, 총 사용 비용이 \(r\) 이하)를 방향간선으로 하는 그래프로 모델링할 수 있다.

이 그래프 위에서의 최단거리를 구해 문제를 해결하자. 이는 dijkstra 알고리즘 등을 이용해 어렵지 않게 해낼 수 있다.

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

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

int N, M, S, E, R;
vector<pair<int, pair<int, int>>> G[101];
int dist[101][101];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[S][0] = 0;
	pq.push(make_pair(0, make_pair(S, 0)));
	while (!pq.empty()) {
		int cur = pq.top().second.first, t = pq.top().first, c = pq.top().second.second; pq.pop();
		if (dist[cur][c] < t) continue;
		for (auto &p : G[cur]) {
			int nxt = p.first, tt = t + p.second.first, cc = c + p.second.second;
			if (cc <= R && tt < dist[nxt][cc]) dist[nxt][cc] = tt, pq.push(make_pair(tt, make_pair(nxt, cc)));
		}
	}
}

int ans;

void solve() {
	ans = 0x3f3f3f3f;
	for (int n = 0; n < N; n++) G[n].clear();
	while (M--) {
		int x, y, t, c; cin >> x >> y >> t >> c;
		G[x].emplace_back(make_pair(y, make_pair(t, c)));
		G[y].emplace_back(make_pair(x, make_pair(t, c)));
	}
	cin >> S >> E >> R;
	dijkstra();
	for (int c = R; c > -1; c--) {
		ans = min(ans, dist[E][c]);
	}
	if (ans < 0x3f3f3f3f) cout << ans << '\n';
	else cout << '\n';
}

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

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

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

이번에 볼 문제는 백준 14265번 문제인 영선 수열이다.
문제는 아래 링크를 확인하자.

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

어떤 수가 홀수이면 1을 빼고 짝수이면 2로 나누는 것을 이진수의 관점에서 해석해보자. 그러면 주어진 수열은 일의자리가 1일 때는 일의자리를 0으로 바꾸고, 아니라면 마지막 0을 지우는 것을 반복하는 것으로 볼 수 있다. 이 과정을 역으로 해석하면, X에서 시작해 Y에 도달하기 위해서는 Y의 자릿수가 (이진수 기준) X로 시작하거나 X가 짝수인 경우 X+1로 시작해야만 함을 알 수 있다.

이를 이용해 Y를 가능한 각 자릿수별로 세어 문제를 해결하자.

구현 방식에 따라 X가 0으로 주어지는 경우에 유의할 필요가 있다.

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

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

ll K, KK, A, B, tmp;
ll ans;

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

	cin >> K >> A >> B; KK = K + 1; B++; tmp = K;
	if (!K) {
		cout << B - A;
		return 0;
	}
	while (K < B) {
		if (A < KK) ans += min(B, KK) - max(A, K);
		K <<= 1, KK <<= 1;
	}
	if (tmp % 2 == 0) {
		K = tmp + 1, KK = tmp + 2;
		while (K < B) {
			if (A < KK) ans += min(B, KK) - max(A, K);
			K <<= 1, KK <<= 1;
		}
	}
	cout << ans;
}

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

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

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

한 방향으로의 시야각 최댓값을 찾을 때 주어지는 꺾이는 점만을 이용해 판단해도 충분함을 관찰하자. 해안가와 해당 점을 잇는 직선을 해안가를 원점으로 하는 직선들로 생각하면 이를 쉽게 이해할 수 있을 것이다.

왼쪽으로의 시야각과 오른쪽으로의 시야각의 최댓값 중 더 큰 값을 찾자.

글쓴이는 tanl값을 좌표를 이용해 계산 후 atan2l함수를 이용해 각도로 변환하여 문제를 해결하였다.

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

#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;

const ld PI = acosl(-1);
int N;
int P[50000][2];
ld X, Y;

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 k = 1; k + 1 < N; k++) {
		int dx = P[k][0] - P[0][0], dy = P[k][1];
		X = max(X, atan2l(dy, dx));
		dx = P[N - 1][0] - P[k][0];
		Y = max(Y, atan2l(dy, dx));
	}

	cout << fixed;
	cout.precision(10);
	cout << max(X, Y) * 180 / PI;
}

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

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

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

먼저 각 칸에서 가장 가까운 delivery office까지의 거리를 multisource bfs를 이용해 계산해 두자.

각 칸의 좌표를 45도 회전시키고 원점으로부터의 거리를 \(\sqrt{2}\)배시켜 새로운 좌표에 대응시켜보자. 이 좌표계에서는 각 칸에 대하여 그 칸의 가장 가까운 delivery office까지의 거리가 어떤 정수 \(K\)에 대하여 그보다 작거나 같게 하기 위해 설치되어야 하는 새 office의 범위를 축에 평행항 변들로 이루어진 직사각형꼴로 나타낼 수 있다. 따라서 이 직사각형들의 교집합(에 포함되는 원래의 점 = 두 좌표의 합이 짝수인 점)의 존재 여부로 원하는 값이 \(K\) 이하가 될 수 있는지 여부를 판단할 수 있게 된다. 

\(K\)의 값을 이분 탐색으로 계산해 문제를 해결하자.

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

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

int R, C;
vector<pair<int, int>> vec[500];
int dist[250][250];
queue<pair<int, int>> que;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
int LL, RR, mx;

int bnsearch() {
    LL = 0, RR = mx;
    while (LL < RR) {
        int mid = (LL + RR) / 2;
        int XL = -1000000007, XR = 1000000007, YL = -1000000007, YR = 1000000007;
        for (int k = mid + 1; k <= mx; k++) {
            for (auto &p:vec[k]) {
                XL = max(XL, p.first - mid);
                XR = min(XR, p.first + mid);
                YL = max(YL, p.second - mid);
                YR = min(YR, p.second + mid);
            }
        }
        if (XL <= XR && YL <= YR) {
            if (XL == XR && YL == YR && (abs(XL + YL) & 1)) LL = mid + 1;
            else RR = mid;
        }
        else LL = mid + 1;
    }
    return LL;
}

void bfs() {
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second; que.pop();
        mx = max(mx, dist[r][c]);
        vec[dist[r][c] - 1].emplace_back(make_pair(r + c, c - r));
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr < 0 || rr >= R || cc < 0 || cc >= C || dist[rr][cc]) continue;
            dist[rr][cc] = dist[r][c] + 1;
            que.push(make_pair(rr, cc));
        }
    }
}
void solve() {
    mx = 0;
    for (int r = 0; r < 500; r++) vec[r].clear();
    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            char x; cin >> x;
            if (x == '1') dist[r][c] = 1, que.push(make_pair(r, c));
            else dist[r][c] = 0;
        }
    }
    bfs();
    cout << bnsearch() << '\n';
}

int T;

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

    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
}

랜덤 마라톤 · 코스 13 F번

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

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

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

T분 뒤에 어떤 칸이 젖어있으려면 어떤 물이 새는 곳까지의 거리가 T-1 이하여야 함을 관찰하자. 단 여기서 두 칸 사이의 거리는 한 칸에서 다른 칸으로 벽이 아닌 인접한 칸으로의 이동만을 이용하여 이동할 때 필요한 최소 이동횟수(단, 이동이 불가능하면 무한대)라 하자.

따라서 물이 새는 칸들을 시점으로 하는 multisource BFS를 돌려 각 칸이 젖기 위한 최소시간을 구해 문제를 쉽게 해결할 수 있다.

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

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

int R, C, T, L, W;

int dist[1002][1002];
queue<pair<int, int>> que;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

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

    while (cin >> R >> C >> T >> L >> W) {
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                dist[r][c] = 0;
            }
        }
        while (L--) {
            int r, c; cin >> r >> c;
            dist[r][c] = 1;
            que.push(make_pair(r, c));
        }
        while (W--) {
            int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
            if (r1 == r2) {
                if (c1 > c2) swap(c1, c2);
                for (int c = c1; c <= c2; c++) dist[r1][c] = 1000000007;
            }
            else if (c1 == c2) {
                if (r1 > r2) swap(r1, r2);
                for (int r = r1; r <= r2; r++) dist[r][c1] = 1000000007;
            }
            else if (r2 - r1 == c2 - c1) {
                if (r1 > r2) swap(r1, r2), swap(c1, c2);
                for (int r = r1, c = c1; r <= r2; r++, c++) dist[r][c] = 1000000007;
            }
            else {
                if (r1 > r2) swap(r1, r2), swap(c1, c2);
                for (int r = r1, c = c1; r <= r2; r++, c--) dist[r][c] = 1000000007;
            }
        }

        while (!que.empty()) {
            int r = que.front().first, c = que.front().second; que.pop();
            for (int i = 0; i < 4; i++) {
                int rr = r + dr[i], cc = c + dc[i];
                if (rr < 1 || rr > R || cc < 1 || cc > C || dist[rr][cc]) continue;
                dist[rr][cc] = dist[r][c] + 1;
                que.push(make_pair(rr, cc));
            }
        }
        
        int ans = 0;
        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                if (dist[r][c] && dist[r][c] <= T) ans++;
            }
        }
        cout << ans << '\n';
    }
}

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

이번에 볼 문제는 백준 10425번 문제인 피보나치 인버스이다.
문제는 아래 링크를 확인하자.

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

적절한 \(10^K\)로 첫 10만개의 피보나치 수를 나눈 나머지를 얻어보면 (첫 두 수를 제외하고) 이 값들이 서로 다름을 확인할 수 있다.

따라서 이를 이용해 첫 10만개의 수를 \(10^K\)로 나눈 나머지를 map 등을 이용해 순서와 대응시켜 문제를 해결할 수 있다.

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

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

int T;
ll A = 1, B = 1;
map<ll, int> mp;

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

    for (int k = 2; k < 100001; k++) {
        A += B;
        swap(A, B);
        if (B > 99999999999999999LL) B -= 100000000000000000LL;
        mp[A] = k;
    }
    
    cin >> T;
    while (T--) {
        string s; cin >> s;
        ll val = 0;
        for (auto &l:s) {
            val = val * 10 + (l - '0');
            val %= 100000000000000000LL;
        }
        cout << mp[val] << '\n';
    }
}