취미로 코딩하기

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

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

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

i번 인덱스의 수와 j번 인덱스의 수의 값중 가장 작은 값의 크기가 x일 때, 적어도 두 수 모두 값이 x 이상이어야 함을 알 수 있다.

주어지는 모든 min값 정보를 위와 같은 정보로 변환해 각 인덱스의 수의 최솟값을 구해 문제를 해결하자. 단, 배열의 모든 수는 양수여야 함에 유의하자.

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

#include <iostream>
using namespace std;

int N, M;
int A[100001];

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

	cin >> N >> M;
	while (M--) {
		int x, y, z; cin >> x >> y >> z;
		A[x] = max(A[x], z), A[y] = max(A[y], z);
	}
	for (int i = 1; i <= N; i++) {
		if (A[i]) cout << A[i] << ' ';
		else cout << 1 << ' ';
	}
}

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

이번에 볼 문제는 백준 14488번 문제인 준오는 급식충이야!!이다.
문제는 아래 링크를 확인하자.

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

각 학생들이 시간 T가 지난 뒤에 있을 수 있는 범위를 폐구간으로 나타낼 때, 해당 폐구간들의 교집합이 공집합인지 아닌지 판별하는 것으로 문제를 해결할 수 있다.

부동소수점 연산을 이용한 문제 해결 방법은 오차로 틀릴 수 있음에 유의하자. 대신 10000을 곱한 정수값을 이용해 계산하여 부동소수점 오차를 피할 수 있다.

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

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

int NN, sidx; string s;
lll N, T;
lll X[50000], V[50000];
lll L, R;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> NN >> s;
	N = NN;
	while (sidx < s.length() && s[sidx] != '.') sidx++;
	if (sidx == s.length()) s += '.';
	while (sidx + 4 >= s.length()) s += '0';
	T = stoll(s.substr(0, s.length() - 5)) * 10000 + stoll(s.substr(s.length() - 4, 4));
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		X[i] = x;
	}
	for (int i = 0; i < N; i++) {
		int v; cin >> v;
		V[i] = v;
	}
	L = -1, R = 1;
	for (int i = 0; i < 120; i++) L *= 2, R *= 2;
	for (int i = 0; i < N; i++) {
		lll lft = X[i] * 10000 - T * V[i];
		lll rgt = X[i] * 10000 + T * V[i];
		L = max(L, lft), R = min(R, rgt);
	}

	if (L <= R) cout << 1;
	else cout << 0;
}

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

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

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

100행100열의 격자에서 정사각형이 되게끔 네 점을 고르는 경우의 수는 충분히 적다(1000만 이하)는 점을 관찰하자.

이 점을 이용하면 가능한 모든 정사각형 네 점의 위치에 한 번씩 접근하여 해당 정사각형을 이룰 수 있는지 확인 및 넓이 계산을 반복하는 완전탐색으로 가능한 정사각형의 넓이의 최댓값을 계산할 수 있다.

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

#include <iostream>
using namespace std;

int N;
char board[100][100];
int ans;

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

    cin >> N;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> board[r][c];
        }
    }

    for (int dr = 0; dr < N; dr++) {
        for (int dc = 0; dr + dc < N; dc++) {
            for (int r = dc; r + dr < N; r++) {
                for (int c = 0; c + dr + dc < N; c++) {
                    int jcnt = 0, bcnt = 0, acnt = 0;
                    if (board[r][c] == 'J') jcnt++;
                    else if (board[r][c] == 'B') bcnt++;
                    else acnt++;
                    if (board[r + dr][c + dc] == 'J') jcnt++;
                    else if (board[r + dr][c + dc] == 'B') bcnt++;
                    else acnt++;
                    if (board[r + dr - dc][c + dc + dr] == 'J') jcnt++;
                    else if (board[r + dr - dc][c + dc + dr] == 'B') bcnt++;
                    else acnt++;
                    if (board[r - dc][c + dr] == 'J') jcnt++;
                    else if (board[r - dc][c + dr] == 'B') bcnt++;
                    else acnt++;

                    if (jcnt == 4 || (jcnt == 3 && acnt == 1)) ans = max(ans, (dr + dc) * (dr + dc) - 2 * dr * dc);
                }
            }
        }
    }
    cout << ans;
}

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

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

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

루트에서 서로 다른 두 리프로 가는 경로에 있는 (탐색하고자 하는) 문자열의 등장 횟수는 (두 리프의 LCA까지의 등장횟수) + (각 경로의 문자를 포함하는 등장횟수)로 생각할 수 있다. 따라서 KMP를 각 노드의 자식별로 이어서 진행하는 것으로 문제를 해결할 수 있다.

경로별로 KMP를 루트부터 다시 시작할 필요가 없음을 확인하자. LCA까지 등장하는 문자는 동일하므로, 실패함수(pi배열)도 동일하기 때문이다.

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

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

int N, ans;
string S; int Slen;
vector<pair<int, string>> G[15000];
int pi[15000015];

void dfs(int cur, int ii) {
    for (auto &p:G[cur]) {
        int nxt = p.first; S += p.second;
        int SSlen = S.length();
        for (int i = ii; i < SSlen; i++) {
            int idx = pi[i - 1];
            while (idx && S[idx] != S[i]) idx = pi[idx - 1];
            if (S[idx] == S[i]) pi[i] = idx + 1;
            else pi[i] = idx;
            if (pi[i] == Slen) ans++;
        }
        dfs(nxt, SSlen);
        int K = p.second.length();
        while (K--) S.pop_back();
    }
}

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

    cin >> N;
    for (int k = 1; k < N; k++) {
        int x, y; string s; cin >> x >> y >> s;
        G[x].emplace_back(make_pair(y, s));
    }

    cin >> S; Slen = S.length(); S += '#';
    for (int i = 1; i <= Slen; i++) {
        int idx = pi[i - 1];
        while (idx && S[idx] != S[i]) idx = pi[idx - 1];
        if (S[idx] == S[i]) pi[i] = idx + 1;
        else pi[i] = idx;
    }
    
    dfs(0, Slen + 1);

    cout << ans;
}

랜덤 마라톤 · 코스 14 F번

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

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