취미로 코딩하기

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

이번에 볼 문제는 백준 10431번 문제인 줄세우기이다.
문제는 아래 링크를 확인하자.

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

기존 줄의 아이들이 키순서대로 서있는 상태라면 새 아이가 규칙에 따라 줄을 서고 난 뒤에도 줄의 아이들이 키순서대로 서있게 된다는 점을 관찰하자. 또한, 초기상태(한 명의 아이가 줄을 서있는 상태)는 아이들이 키순서대로 서있는 상태로 생각할 수 있음을 관찰하자. 이 관찰을 이용하면 줄의 아이들은 항상 키순서대로 서있는 상태가 됨을 알 수 있다.

위의 성질을 바탕으로 생각하면, 새 아이가 줄에 들어올 때 뒤로 물러서게 되는 아이들은 정확히 새 아이보다 키가 큰 아이들과 같다는 점을 알 수 있다. 이를 이용해 새 아이를 줄에 추가할 때마다 먼저 들어온 아이들 중 새 아이보다 키가 큰 아이들의 수를 모두 합하는 것으로 문제의 답을 구할 수 있다.

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

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

int P;

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

	cin >> P;
	while (P--) {
		int T, ans = 0; cin >> T;
		vector<int> vec;
		for (int i = 0; i < 20; i++) {
			int x; cin >> x;
			for (auto& k : vec) {
				if (x < k) ans++;
			}
			vec.emplace_back(x);
		}

		cout << T << ' ' << ans << '\n';
	}
}

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

이번에 볼 문제는 백준 28141번 문제인 Easy Interactive Problem이다.
문제는 아래 링크를 확인하자.

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

1 이상 N 이하의 정수 \(b_0\)에 대하여 수열 \(b_i = A_{b_{i-1}}\)은 일정한 주기로 반복되는 수열이 됨을 관찰하자.

이 수열의 주기가 1이라면 모든 p에 대하여 \(b_p = b_0\)이 된다.

이 수열의 주기가 1이 아니라 가정하자. 그렇다면  수열의 주기의 배수가 아닌 수 p에 대하여 항상 \(b_p \neq b_0\)이 성립한다. 이제 \(b_p\)부터 수열의 다음 수를 찾는 것을 반복하는 것으로 원래의 순열을 구해낼 수 있게 된다.

위와 같은 아이디어를 이용해 순열을 구하고 문제를 해결하자. 이 때 질문 횟수가 3N/2 이하가 됨은 주기가 1인 사이클의 경우 필요 질문횟수가 1, 그 외의 경우 필요 질문횟수가 k+1(단, k는 사이클의 크기)임을 이용해 간단히 보일 수 있다.

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

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

int N;
bool sieve[1000000];

queue<int> primeque;

void init() {
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000000; j += i) sieve[j] = 1;
	}
	for (ll i = 5001; i < 1000000; i += 2) {
		if (sieve[i]) continue;
		primeque.push(i);
	}
}

int ans[1001];
int qnum = -1;

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

	init();

	cin >> N;
	for (int i = 1; i <= N; i++) {
		if (ans[i]) continue;
		while (qnum >= primeque.front()) primeque.pop();
		qnum = primeque.front();

		int ii, iii; queue<int> que;
		cout << '?' << ' ' << i << ' ' << qnum++ << endl;
		cin >> ii; que.push(ii);
		iii = ii;

		if (i != ii) {
			cout << '?' << ' ' << i << ' ' << qnum++ << endl;
			cin >> ii; que.push(ii);

			while (ii != iii) {
				cout << '?' << ' ' << i << ' ' << qnum++ << endl;
				cin >> ii; que.push(ii);
			}

			que.pop();
		}

		int cur = iii;
		while (!que.empty()) {
			ans[cur] = que.front();
			cur = que.front();
			que.pop();
		}
	}

	cout << '!';
	for (int i = 1; i <= N; i++) cout << ' ' << ans[i];
	cout << endl;
}

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

이번에 볼 문제는 백준 28140번 문제인 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열의 각 i번째 문자에 대하여 i 이상의 인덱스에서 등장하는 첫 번째 'B'는 몇 번째 인덱스인지, 'R'은 몇 번째 인덱스인지를 각각 저장해둔 배열을 만든다면 그리디한 알고리즘을 이용해 문제를 간단히 해결할 수 있다. 구체적으로, [l,r] 구간이 주어질 때 l부터 살폈을 때 가장 먼저 나오는 'R'의 인덱스 r1, r1+1부터 살폈을 때 가장 먼저 나오는 'R'의 인덱스 r2, r2+1부터 살폈을 때 가장 먼저 나오는 'B'의 인덱스 b1, b1+1부터 살폈을 때 가장 먼저 나오는 'B'의 인덱스 b2를 구했을 때 b2가 [l,r]에 속하는지를 살피는 것으로 문제를 해결할 수 있게 된다. 이 과정에서 그 뒤로 'B' 또는 'R'이 등장하지 않는 경우에 대한 예외처리를 적절히 해야 함에 유의하자.

위의 과정을 위한 배열은 문자열을 거꾸로 한 문자씩 살펴나가는 것으로 쉽게 구할 수 있다. 글쓴이는 disjoint set을 이용한 방법으로 해당 배열을 구하였다.

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

#include <iostream>
using namespace std;

int N, Q;
int arrR[1000004], arrB[1000004];

int findR(int i) {
	if (arrR[i] == i) return i;
	else return arrR[i] = findR(arrR[i]);
}

int findB(int i) {
	if (arrB[i] == i) return i;
	else return arrB[i] = findB(arrB[i]);
}

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

	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		char c; cin >> c;
		if (c != 'R') arrR[i] = i + 1;
		else arrR[i] = i;
		if (c != 'B') arrB[i] = i + 1;
		else arrB[i] = i;
	}
	for (int i = 0; i < 4; i++) arrR[N + i] = arrB[N + i] = N + i;

	while (Q--) {
		int L, R; cin >> L >> R;
		int ans1 = findR(L);
		int ans2 = findR(ans1 + 1);
		int ans3 = findB(ans2 + 1);
		int ans4 = findB(ans3 + 1);
		if (ans4 > R) cout << -1 << '\n';
		else cout << ans1 << ' ' << ans2 << ' ' << ans3 << ' ' << ans4 << '\n';
	}
}

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

이번에 볼 문제는 백준 28139번 문제인 평균 구하기이다.
문제는 아래 링크를 확인하자.

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

모든 방문방법의 경우의 수는 N!가지이고, 각 방문방법은 N-1개의 방향에지로 구성되어 있음을 관찰하자. 또한 모든 방문방법에 포함된 각 방향에지의 개수는 전부 같음을 관찰하자.

위의 관찰을 이용하면 (모든 방향에지의 길이의 합)을 (방향에지의 개수)/(N-1)로 나누어 문제에서 찾는 기댓값을 구할 수 있음을 알 수 있다. 여기서 사람 A에서 B로 향하는 것을 나타내는 방향에지와 B에서 A로 향하는 것을 나타내는 방향에지는 서로 다른 에지임에 유의해 계산하자.

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

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

ld ans;

int N;
int coord[5000][2];

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> coord[i][0] >> coord[i][1];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int dx = (coord[i][0] - coord[j][0]), dy = (coord[i][1] - coord[j][1]);
			ans += sqrt(dx * dx + dy * dy);
		}
	}

	cout << fixed;
	cout.precision(10);

	cout << ans / N;
}

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

이번에 볼 문제는 백준 28138번 문제인 재밌는 나머지 연산이다.
문제는 아래 링크를 확인하자.

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

양의 정수 N을 M으로 나누었을 때 나머지가 R이면 N-R을 M으로 나누었을 때의 나머지는 0이 됨을 알 수 있다. 즉 M은 N-R의 약수여야 함을 알 수 있다. 또한 M으로 나눈 나머지가 R이라는 점에서 M은 R보다 큰 정수여야 함을 알 수 있다.

모든 N-R의 양의 약수 중 R보다 큰 수들의 합을 구해 문제를 해결하자. 모든 약수 k는 N-R 또는 (N-R)/k가 100만 이하가 됨을 이용하면 문제를 해결할 수 있을 것이다. 이 때 N-R이 제곱수인 경우 그 제곱근이 합에 중복되게 들어가지 않아야 함에 유의해 구현하자.

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

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

ll N, R;
ll ans, i = 1;

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

	cin >> N >> R;
	N -= R;

	for (; i * i < N; i++) {
		if (N % i) continue;
		if (i > R) ans += i;
		if (N / i > R) ans += N / i;
	}

	if (i * i == N && i > R) ans += i;

	cout << ans;
}

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

이번에 볼 문제는 백준 12931번 문제인 두 배 더하기이다.
문제는 아래 링크를 확인하자.

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

길이 1의 배열의 경우, 즉 수 하나짜리 배열을 연산을 최소한으로 이용해 만드는 방법을 생각해보자. 이는 주어진 수를 이진수로 표현해 msb부터 차례대로 1인 경우 1 더하기 연산을 한 뒤 다음 비트가 더 존재하면 2를 곱하는 것을 반복하는 것으로 해낼 수 있다.

주어진 배열에서 가장 자릿수가 많은 이진수를 X라 하자. 이 때, 이 수를 빠르게 생성하기 위해서는 이 수의 자릿수에 비례하는 횟수만큼 배열의 원소를 2배하는 연산을 사용해야 할 것임을 관찰할 수 있다. 이 때, 이 2배연산 순서의 사이사이에 배열의 다른 원소의 자릿수를 1을 적절히 더해나간다면 얻고자 하는 배열을 배열을 최소한의 2배연산을 이용해 만들 수 있음을 알 수 있다.

한편, 각 수에 대하여 해당 수를 표현하기 위해서는 적어도 각 수를 이진수로 표현했을 때 1이 나타나는 횟수만큼의 +1 연산을 해야 함을 관찰하면 위의 방법이 최소 연산횟수로 주어진 배열을 얻는 방법임을 알 수 있다.

위의 관찰들을 이용해 문제를 해결해주자.

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

#include <iostream>
using namespace std;

int N;
int msb, cnt;

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

	cin >> N;
	while (N--) {
		int mcnt = 0;
		int x; cin >> x;
		while (x) {
			mcnt++;
			cnt += x & 1;
			x >>= 1;
		}
		msb = max(msb, mcnt);
	}

	if (msb) cout << msb + cnt - 1;
	else cout << 0;
}