취미로 코딩하기

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

이번에 볼 문제는 백준 24649번 문제인 Letters Q and F이다.
문제는 아래 링크를 확인하자.

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

주어진 Q와 F의 모양은 두 번째 열의 첫째 행부터 셋째 행까지를 중점적으로 볼 때 항상 검은칸-흰칸-검은칸 구조를 가지고 있어야 함을 관찰하자.

위 관찰을 이용하면, 오른쪽부터 색칠된 칸들을 살펴볼 때 검은칸-흰칸-검은칸 구조가 나올 때마다 이 구조가 Q에 포함되는 구조일 수 있는지 먼저 판단하고, 그 다음으로 이 구조가 F에 포함될 수 있는 구조인지 판단하는 것을 반복해나가는 것으로 문제를 해결할 수 있음을 유추할 수 있다. Q에 포함될 수 있는 구조인데 지나치면 Q에 포함되는 마지막 열 검은 칸이 이후에 어떤 문자에도 포함될 수가 없어짐을 확인하자. 이와 유사하게 F의 경우도 정당성을 보일 수 있다.

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

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

int R, C;
string board[300];
int Q, F;

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int c = C - 2; c > 0; c--) {
		for (int r = 1; r + 3 < R; r++) {
			if (board[r - 1][c] == '#' && board[r][c] == '.' && board[r + 1][c] == '#') {
				if (board[r][c + 1] == '#') {
					if (board[r - 1][c - 1] == '#' && board[r - 1][c] == '#' && board[r - 1][c + 1] == '#' && board[r][c - 1] == '#' && board[r][c + 1] == '#' && board[r + 1][c - 1] == '#' && board[r + 1][c] == '#' && board[r + 1][c + 1] == '#' && board[r + 2][c + 1] == '#' && board[r + 3][c + 1] == '#') {
						Q++;
						board[r - 1][c - 1] = board[r - 1][c] = board[r - 1][c + 1] = board[r][c - 1] = board[r][c + 1] = board[r + 1][c - 1] = board[r + 1][c] = board[r + 1][c + 1] = board[r + 2][c + 1] = board[r + 3][c + 1] = '.';
					}
				}
				else {
					if (board[r - 1][c - 1] == '#' && board[r - 1][c] == '#' && board[r - 1][c + 1] == '#' && board[r][c - 1] == '#' && board[r + 1][c - 1] == '#' && board[r + 1][c] == '#' && board[r + 2][c - 1] == '#' && board[r + 3][c - 1] == '#') {
						F++;
						board[r - 1][c - 1] = board[r - 1][c] = board[r - 1][c + 1] = board[r][c - 1] = board[r + 1][c - 1] = board[r + 1][c] = board[r + 2][c - 1] = board[r + 3][c - 1] = '.';
					}
				}
			}
		}
	}

	cout << Q << ' ' << F;
}

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

이번에 볼 문제는 백준 11541번 문제인 At most twice이다.
문제는 아래 링크를 확인하자.

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

주어진 수보다 작거나 같은 수중 각 자리에 등장하는 숫자들의 등장횟수가 2회 이하가 되는 가장 큰 수를 찾는 문제이다.

주어진 수가 조건을 만족할 때까지 most significant digit(가장 왼쪽 자리)부터 읽으면서 처음으로 등장횟수가 3회째 되는 숫자가 등장하면 (1) 해당 자리에 등장하게 되는 수가 2회 이하 등장한 수가 될 때까지 1씩 감소시키고 (2) 그 숫자가 '0'보다 작아졌다면 앞자리의 숫자들로 구성된 숫자열을 정수로 생각해 1을 뺀 다음 뒤의 모든 자릿수를 '9'로 변경, 그렇지 않다면 그리디하게 사용할 수 있는 가장 큰 숫자부터 차례대로 이용해 뒤의 문자열을 채우는 것을 반복하자. 단, 이 과정에서 주어진 수가 leading zero를 가지면 안되므로 각 단계에서 leading zero를 가지는 수가 나타날 경우 그 zero를 제거해주자.

과정 (2)의 첫 번째 경우에서 단순히 뒤의 모든 자릿수를 '9'로 변경한 이유는 1을 뺀 앞의 자릿수들이 조건(모든 숫자들은 2회 이하 등장)을 만족하는지 다시 확인할 필요가 있기 때문에 두 번째 경우의 과정을 단순히 생략하고 가능한 가장 큰 수를 나타내게끔 각 자리를 조정한 것으로 큰 의미가 있지는 않다.

이 과정은 수가 점점 작아지므로 항상 종료되는 것이 보장되며, 특히 그 반복 횟수가 충분히 적음(1을 빼고 앞의 자릿수를 다시 점검하는 횟수는 자릿수에 비례한 횟수만큼만 일어날 수 있음)을 어렵지 않게 관찰할 수 있다. 따라서 위의 알고리즘은 문제를 해결하기에 충분히 빠름을 알 수 있다.

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

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

int cnt[128];
int slen;
string s;

bool chk3() {
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < slen; i++) {
		cnt[s[i]]++;
		if (cnt[s[i]] == 3) return 1;
	}
	return 0;
}

void func() {
	if (s.front() == '0') {
		s = s.substr(1, slen - 1);
		slen--;
		return;
	}
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < slen; i++) {
		cnt[s[i]]++;
		if (cnt[s[i]] < 3) continue;
		
		while (cnt[s[i]] == 3) {
			cnt[s[i]]--;
			s[i]--;
			cnt[s[i]]++;
		}
		if (s[i] < '0') {
			s[i] = '9';
			for (int j = i - 1; j > -1; j--) {
				s[j]--;
				if (s[j] < '0') s[j] = '9';
				else break;
			}
			for (int j = i + 1; j < slen; j++) s[j] = '9';
		}
		else {
			char idx = '9';
			for (int j = i + 1; j < slen; j++) {
				while (cnt[idx] > 1) idx--;
				s[j] = idx;
				cnt[idx]++;
			}
		}
		break;
	}
}

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

	cin >> s; slen = s.length();
	if (s.length() > 18) s = "999999999999999999", slen = 18;
	while (chk3() || s.front() == '0') func();
	cout << s;
}

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

이번에 볼 문제는 백준 27730번 문제인 견우와 직녀이다.
문제는 아래 링크를 확인하자.

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

오작교를 이을 \(E\)의 정점 번호를 \(e\), \(W\)의 정점 번호를 \(w\)라 하자. 이 때 \(E\)와 \(W\)의 정점 쌍 사이의 거리의 총합을 (1) \(E\)의 각 정점으로부터 \(e\)로 이동을 \(W\)의 정점의 개수만큼, (2) \(e\)에서 \(w\)로 이동을 \(E\)와 \(W\)의 정점 쌍의 개수만큼, , (3) \(w\)로부터 \(W\)의 각 정점으로 이동을 \(E\)의 정점의 개수만큼 하는 것으로 나누어 생각해보자. 이 중 \(E\)와 \(W\)의 크기는 주어지는 값으로 고정되므로, 주어진 트리에서 모든 정점까지의 거리의 총합이 가장 작은 정점을 찾을 수 있다면 문제를 해결할 수 있게 된다.

트리에서 모든 정점까지의 거리의 총합이 가장 작은 정점을 찾아 문제를 해결하자. 이는 DP를 이용해 어렵지 않게 구할 수 있다.

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

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

ll N;
vector<pair<int, ll>> G[100001];
ll streecnt[100001];
ll dp[100001];
ll dp2[100001];
void func(int cur, int par) {
    ll &val = dp[cur] = 0;
    streecnt[cur] = 1;
    for (auto &p:G[cur]) {
        if (p.first == par) continue;
        func(p.first, cur);
        val += streecnt[p.first] * p.second + dp[p.first];
        streecnt[cur] += streecnt[p.first];
    }
}

void func2(int cur, int par, ll pval) {
    if (!par) dp2[cur] = dp[cur];
    else {
        dp2[cur] = dp2[par] - streecnt[cur] * pval + (N - streecnt[cur]) * pval;
    }
    for (auto &p:G[cur]) {
        if (p.first == par) continue;
        func2(p.first, cur, p.second);
    }
    
}
ll anode1, aval1, sz1, anode2, aval2, sz2;

void solve(ll &an, ll &av, ll &z) {
    cin >> N; z = N;
    for (int i = 1; i <= N; i++) G[i].clear();
    memset(streecnt, 0, sizeof(streecnt));
    for (int i = 1; i < N; i++) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }

    func(1, 0);
    func2(1, 0, 0);
    av = 1000000000000000007LL;
    for (int i = 1; i <= N; i++) {
        if (dp2[i] < av) av = dp2[i], an = i;
    }
}

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

    solve(anode1, aval1, sz1);
    solve(anode2, aval2, sz2);
    cout << anode1 << ' ' << anode2 << '\n';
    cout << aval1 * sz2 + aval2 * sz1 + sz1 * sz2;

}

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

이번에 볼 문제는 백준 30512번 문제인 조용히 완전히 영원히이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 이 문제를 쿼리를 \(L\) 기준으로 정렬 후 sweeping하는 방향으로 접근하였다.

\(A_1\)부터 \(A_N\)까지 수열을 구성하는 수를 하나씩 차례대로 보면서 문제를 해결해보자.

이 과정에서 각 \(i\)번째 수를 포함하는 쿼리는 \(i-1\)번째 수를 포함하는 구간쿼리에서 \(i-1\)번째 수까지만 포함하는 쿼리를 제외 및 \(i\)번째 수부터 포함하는 쿼리를 추가한 쿼리들로 구성되어 있음을 관찰하자. 또한 이러한 쿼리의 추가 및 제외는 총 \(2N\)번 이하로 나타남을 관찰하자.

한편, 이와 같은 쿼리 중 해당 수에 마지막으로 유의미하게 적용되었을 수 있는 쿼리는 (1) 적용하고자 하는 \(x\)값이 가장 작은 쿼리, 그러한 쿼리가 여러 개면 (2) 가장 먼저 적용된 쿼리 하나만 확인해도 충분함을 관찰하자. 그 이전에 적용한 쿼리는 해당 쿼리로 무조건 그 덮어씌워질 것이고, 그 이후의 쿼리는 해당 쿼리의 결과를 바꾸지 못할 것이기 때문이다. 물론, 해당 쿼리도 값을 바꾸지 못하는 경우도 존재하는데(원래 값이 매우 작았던 경우가 이에 해당한다.), 이 경우에는 어떤 쿼리도 값을 바꾸지 않는다는 것을 알 수 있다.

위와 같은 쿼리의 추가, 제거 및 탐색은 우선순위 큐(Priority Queue)를 이용해 어렵지 않게 구현할 수 있다.

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

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

int N, Q;
int A[100001];
priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
priority_queue<pair<pair<int, int>, int>> pq2;
int ans[100001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	cin >> Q;
	for (int q = 1; q <= Q; q++) {
		int L, R, V; cin >> L >> R >> V;
		pq.push(make_pair(make_pair(-L, R), make_pair(V, q)));
	}
	for (int i = 1; i <= N; i++) {
		while (!pq.empty() && pq.top().first.first == -i) {
			pq2.push(make_pair(make_pair(-pq.top().second.first, -pq.top().second.second), pq.top().first.second));
			pq.pop();
		}
		while (!pq2.empty() && pq2.top().second < i) pq2.pop();
		if (!pq2.empty()) {
			if (-pq2.top().first.first < A[i]) ans[-pq2.top().first.second]++, A[i] = -pq2.top().first.first;
			else ans[0]++;
		}
		else ans[0]++;
	}
	for (int i = 1; i <= N; i++) cout << A[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= Q; i++) {
		ans[i] += ans[i - 1];
		cout << ans[i] << ' ';
	}
}

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

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

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

두 촛불의 좌표가 서로 다르므로, 두 촛불의 x좌표 또는 y좌표는 서로 다름을 알 수 있다. 일반성을 잃지 않고 x좌표가 서로 다르다고 가정해보자. 이 경우 두 촛불의 x좌표가 각각 \(a\)와 \(b\)라면, 케이크의 윗변과 아랫변에서 x좌표가 각각 \(a\)와 \(b\)인 지점을 잇는 직선으로 케이크를 항상 두 촛불이 다른 조각에 올라가게 할 수 있다.

y좌표가 서로 다르더라도 같은 방식으로 문제를 해결할 수 있다.

위의 관찰을 이용해 문제를 해결하는 코드를 작성하자.

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

#include <iostream>
using namespace std;

int X, Y, X1, Y1, X2, Y2;

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

	cin >> X >> Y >> X1 >> Y1 >> X2 >> Y2;
	if (X1 != X2) {
		cout << X1 << ' ' << 0 << ' ' << X2 << ' ' << Y;
	}
	else {
		cout << 0 << ' ' << Y1 << ' ' << X << ' ' << Y2;
	}
}

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

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

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

Steinhaus-Johnson-Trotter Algorithm은 인접한 원소 한 쌍의 swap만으로 다음 순열을 생성하는 방식으로 모든 순열을 정확히 한 번씩 생성하는 알고리즘이다. 이 알고리즘의 다음 원소 생성 방식은 문제에 주어진 연산의 제약 내에서 항상 실행 가능하므로 해당 알고리즘의 순열생성방식을 따라 모든 순열을 출력하는 것으로 문제를 충분히 해결할 수 있다.

Steinhaus-Johnson-Trotter Algorithm은 브루트포스 및 순열과 조합을 공부할 때 한번쯤 봤을 법한 기초 알고리즘이므로 이것이 가장 쉬운 풀이가 아닐까 한다.

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

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

int N;
vector<string> vec[9];

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

    vec[1].emplace_back("1");
    for (int i = 2; i < 9; i++) {
        char c = ('0' + i);
        int sgn = 1;
        for (auto &x:vec[i - 1]) {
            if (sgn) {
                for (int len = i - 1; len >= 0; len--) {
                    string tmp = x.substr(0, len);
                    tmp += c;
                    tmp += x.substr(len, i - 1 - len);
                    vec[i].emplace_back(tmp);
                }
            }
            else {
                for (int len = 0; len < i; len++) {
                    string tmp = x.substr(0, len);
                    tmp += c;
                    tmp += x.substr(len, i - 1 - len);
                    vec[i].emplace_back(tmp);
                }
            }
            sgn ^= 1;
        }
    }
    cin >> N;
    for (auto &s:vec[N]) {
        for (auto &l:s) cout << l << ' ';
        cout << '\n';
    }
}