취미로 코딩하기

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

이번에 볼 문제는 백준 13268번 문제인 셔틀런이다.
문제는 아래 링크를 확인하자.

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

지훈이는 거리 100을 주기로 같은 움직임을 반복한다는 점을 관찰하자.

위 관찰을 이용하면 첫 100만큼 움직일 동안의 지훈이의 위치를 미리 계산하는 것으로 문제를 해결할 수 있음을 알 수 있다.

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

#include <iostream>
using namespace std;

int N;
int ans[100] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
				0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
				0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
				0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1
};

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

	cin >> N;
	N %= 100;

	cout << ans[N];
}

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

이번에 볼 문제는 백준 2986번 문제인 파스칼이다.
문제는 아래 링크를 확인하자.

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

주어진 프로그램은 N-1의 값을 N의 약수가 될 때까지 1씩 줄여나가는 프로그램이다. 즉, N의 자기 자신이 아닌 가장 큰 약수가 될 때까지 N-1의 값을 1씩 줄여나가는 프로그램이다. 단, 1의 경우 반복문을 한 바퀴도 돌지 못하므로 답은 0이 된다.

N의 자기 자신이 아닌 가장 큰 약수를 찾아 문제를 해결하자. N이 소수이면 찾고자 하는 약수는 1이 될 것이다. 그렇지 않은 경우 N을 해당 약수로 나눈 수는 N의 제곱근 이하임을 이용해 1이 아닌 가장 작은 약수를 반복문으로 찾는 것으로 문제를 충분히 해결할 수 있다.

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

#include <iostream>
using namespace std;

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

	cin >> N;
	ans = N - 1;

	for (int i = 2; i * i <= N; i++) {
		if (N % i) continue;
		ans = N - N / i;
		break;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 17619번 문제인 개구리 점프이다.
문제는 아래 링크를 확인하자.

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

주어진 통나무들을 왼쪽 끝 좌표 순서대로 먼저 정렬하자. 그리고 차례대로 읽어나가면서 이번 통나무가 이전에 등장한 통나무와 겹치는지를 확인해나가자. 이 때 매 차례마다 그 때까지 확인한 통나무의 오른쪽 끝이 어디인지를 기록해나가면 이전에 등장한 통나무와 겹치는지를 쉽게 확인할 수 있다.

이제 겹치는 통나무들 사이의 관계를 집합으로 생각해 주어진 문제를 disjoint set 자료구조를 이용해 간단하게 해결하자.

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

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

int arr[100001];

int findf(int x) {
	if (x == arr[x]) return x;
	return arr[x] = findf(arr[x]);
}

int N, Q;
pair<pair<int, int>, int> logs[100000];

int cur = -1, R = -1;

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

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) arr[i] = i;

	for (int i = 0; i < N; i++) {
		cin >> logs[i].first.first >> logs[i].first.second >> logs[i].second;
		logs[i].second = i + 1;
	}

	sort(logs, logs + N);

	for (int i = 0; i < N; i++) {
		if (R < logs[i].first.first) cur = logs[i].second, R = logs[i].first.second;
		else R = max(R, logs[i].first.second), arr[logs[i].second] = cur;
	}

	while (Q--) {
		int x, y; cin >> x >> y;
		cout << (findf(x) == findf(y)) << '\n';
	}
}

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

이번에 볼 문제는 백준 18115번 문제인 카드 놓기이다.
문제는 아래 링크를 확인하자.

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

카드를 내려놓는 과정을 거꾸로 따라가면서 원래의 카드 뭉치를 구하자. 예를 들어 수현이가 기술을 사용한 순서를 거꾸로 따라가면서 1번 기술을 썼었다면 바닥에 놓인 가장 위의 카드를 카드 뭉치의 가장 위로 올리는 식으로 원래의 카드 뭉치를 구하자.

이 때 카드 상태를 deque 자료구조로 관리하면 카드를 한 장 돌려놓을 때마다 \(O(1)\)의 연산으로 이전 카드 뭉치를 나타낼 수 있다.

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

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

int N;
vector<int> vec;
deque<int> dq;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> vec.emplace_back(i);

	for (int n = 1; n <= N; n++) {
		if (vec.back() == 1) dq.push_back(n);
		else if (vec.back() == 2) {
			int tmp = dq.back(); dq.pop_back();
			dq.push_back(n);
			dq.push_back(tmp);
		}
		else dq.push_front(n);

		vec.pop_back();
	}

	while (!dq.empty()) {
		cout << dq.back() << ' ';
		dq.pop_back();
	}
}

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

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

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

\((a_{i-1} + a_{i+1})/2 \ge a_i \) 가 항상 성립해야 하므로 양 끝 자릿수가 아닌 \(a_i\)가 \(a_{i-1}\)에서 양수 \(d\) 감소한 수라면 \(a_{i_1}\)은 \(a_i\)보다 \(d\)보다 덜 감소한 수여야 함을 관찰하자. 증가의 경우에도 이와 비슷한 관찰을 할 수 있다.

이 관찰에 따르면 하나의 수에서 감소가 4번 일어나려면 \(a_1\)에서 자릿수가 적어도 10은 떨어져야 함을 알 수 있다. 이는 10개의 자릿수밖에 없는 10진수에서는 가능하지 않으므로 하나의 수에서 연속한 감소는 많아야 3번 일어남을 알 수 있다. 이는 증가에서도 마찬가지로 적용된다. 물론 각 자리의 수가 증가하다가 감소(혹은 유지)해도 당연히 조건을 만족시키지 못한다.

위의 관찰을 토대로 가능한 경우의 답을 구해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N == 1) cout << "9";
	else if (N == 2) cout << "99";
	else if (N == 3) cout << "989";
	else if (N == 4) cout << "9889";
	else if (N == 5) cout << "97679";
	else if (N == 6) cout << "976679";
	else if (N == 7) cout << "9643469";
	else if (N == 8) cout << "96433469";
	else cout << -1;
}

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

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

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

문자열에 추가되는 새 문자가 기존 문자열에 이미 사용된 문자라면 학생들은 "Wipe it!"을 외쳐 그 문자를 지우게 됨을 관찰하자. 반대로 문자열에 추가되는 새 문자가 기존 문자열에 사용된 적 없는 문자라면 기존 문자열에 해당 문자를 포함하는 부분문자열이 존재하지 않으므로 "Wipe it!"을 외치지 않음을 관찰하자.

위의 분류는 새 문자를 추가할 때 일어날 수 있는 모든 경우를 포함한다. 따라서 새 문자가 입력될 때마다 기존에 사용한 적이 있는지만을 확인해 그 문자의 출력 여부를 결정하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

char l;
bool visited[128];

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

	while (cin >> l) {
		if (!visited[l]) visited[l] = 1, cout << l;
	}
}