취미로 코딩하기

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

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

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

주어지는 점의 좌표의 범위와 출력해도 되는 점의 좌표의 범위가 10배 차이가 나게 주어진 것이 큰 힌트이다.

각 점 \((x,y)\)을 \((x+1,y+300000000)\)과 대응시키면, 입력으로 주어지는 모든 점은 입력으로 주어질 수 없는(그리고 출력 범위에 포함되는) 점과 일대일 대응되며, 각 대응된 선분은 서로 겹치지 않음을 어렵지 않게 확인할 수 있다.

위와 같이 대응되는 점을 출력하여 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x, y; cin >> x >> y;
		cout << i << ' ' << x + 1 << ' ' << y + 300000000 << '\n';
	}
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

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

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

캥거루가 \(x\)에 있을 때, 한 번 움직인 뒤에 캥거루가 있게 되는 곳은 \(x^2\)과 같다는 점을 관찰하자. (\(n\)보다 크다면 그렇지 않게 될 때까지 \(n\)을 빼는 것을 반복한다.\)

\(n\)과 \(x\)가 공통 소인수 \(g\)를 가진다면 아무리 이동해도 \(x\)는 g의 배수가 되므로 \(x\)는 1이 될 수 없다. 이 뒤로는 \(n\)과 \(x\)가 공통 소인수를 갖지 않는 경우(즉, 서로소인 경우)만을 생각한다.

\(x\)에 있는 캥거루가 이동을 \(r\)번 하면 있게 되는 위치는 \(\mod n\)에 대하여 \(x^{2^r}\)과 합동이다. 따라서 문제의 조건을 만족하려면 \(2^r\)은 \(x\)의 위수(order)의 배수여야 한다. 따라서, 라그랑주 정리(Lagrange's Theorem)를 같이 이용하면 \(n\) 미만의 2의 거듭제곱 형태의 수가 \(x\)의 위수인지 판단하는 것으로 문제를 충분히 해결할 수 있다.

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

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

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

ll AA, BB; lll A, B;

void solve() {
	cin >> AA >> BB;
	if (gcd(AA, BB) > 1) {
		cout << "impossible\n";
		return;
	}
	int ans = 0;
	A = AA, B = BB;
	for (int k = 0; k < 100; k++) {
		if (B == 1) {
			cout << ans << '\n';
			return;
		}
		B = B * B % A;
		ans++;
	}
	cout << "impossible\n";
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

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

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

어떤 하나의 색으로 칠해진 행이 \(k\)개라면, 국기를 회전시켜 얻은 모양에서 그 색으로 칠해져야 하는 열의 개수는 \(k\)개가 된다. 따라서 이 색으로 칠해진 칸 중 색을 다시 칠할 필요가 없는 칸은 \(k^2\)개가 된다. 또한 그 외의 해당 색으로 칠해진 칸은 모두 색을 다시 칠해야 한다.

각각의 색에 대하여 그 색이 칠해진 행의 개수를 이용해 색을 다시 칠할 필요가 없는 칸의 개수를 구하고, 전체 칸의 개수에서 이 값을 빼 문제를 해결하자.

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

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

ll N; ll ans, cnt; int old;
int A[200000];

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);
	for (int i = 0; i < N; i++) {
		if (old == A[i]) cnt++;
		else {
			ans += cnt * cnt;
			cnt = 1;
			old = A[i];
		}
	}
	ans += cnt * cnt;
	cout << N * N - ans;
}

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

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

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

문제에서 구하고자 하는 수는 사면체수(tetrahedral number)과 같다. 사면체수 공식을 이용해 답을 출력해주자.

사면체수를 모르더라도, 윗 층서부터 한 층씩 아래로 내려오며 삼각형을 구성하는 구의 개수를 한 변수에 차례대로 더해나가는 것으로도 답을 구할 수 있을 것이다.

문제의 답을 32비트 정수 자료형에 담을 수 없을 수 있다. 이 점에 유의해 구현하자.

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

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

ll N;

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

	cin >> N;
	cout << N * (N + 1) * (N + 2) / 6;
}

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

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

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

\(i\)번째 꽃까지 보았을 때 마야가 현재 도달할 수 있는 높이의 범위가 \(L\) 이상 \(R\) 이하라고 가정해보자. 이 때 높이가 \(H\)인 \(i+1\)번째 꽃을 보았을 때 해당 꽃에 도달이 가능하다면 \(L\)과 \(R\)은 각각 \(\min(L,H-K)\)와 \(\max(R,H+K)\)가 될 것이고, 그렇지 않다면 \(L\)과 \(R\)은 그대로 유지될 것이다.

초기상태(첫 꽃에 마야가 있는 상태)에서 도달할 수 있는 위치의 범위는 하나의 닫힌 구간으로 나타낼 수 있고 과정을 반복해도 상태는 닫힌 구간으로 나타나므로, 위의 과정을 통해 각 꽃에 마야가 도달할 수 있는지를 항상 판정할 수 있다.

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

#include <iostream>
using namespace std;

int N, K, L, R;

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

	cin >> N >> K >> L;
	R = L;
	L -= K, R += K;
	cout << 1;
	for (int i = 1; i < N; i++) {
		int x; cin >> x;
		if (x < L || R < x) cout << ' ' << 0;
		else {
			cout << ' ' << 1;
			L = min(L, x - K), R = max(R, x + K);
		}
	}
}

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

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

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

읽을 \(N\)개의 문자열의 개수를 인수로 넘겨주는 초기화 함수와 각 문자열을 구성하는 문자 중 알파벳 대문자를 소문자로 바꿔 리턴하는 함수를 작성하는 문제이다.

어차피 대소문자 변환 함수는 채점기가 알아서 \(N\)번 호출하므로 전자는 아무런 행동도 하지 않아도 됨을 확인하자.

주어지는 알파벳 문자 중 대문자를 소문자로 바꾸는 것은 tolower 함수를 이용해 간단히 해낼 수 있다.

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

#include "timecard.h"
#include <string>
using namespace std;

void init(int n) {

}

string convert(string s) {
	for (auto &l:s) l = tolower(l);
	return s;
}