[AtCoder] ABC296 A~D 업솔빙

---

안녕하세요 Gliver 입니다.

이번 글은 앳코더 ABC296에 대해 업솔빙하는 글입니다.

 

 

A번

  - 단순 구현 문제이다.

B번

  - 단순 구현 문제이다.

C번

  - 약간의 사고력을 요구하는 문제이다.

  - 정렬을 하여 답이 되는 경우를 효율적으로 탐색하면 된다.

D번

  - 구현은 어렵지 않으나, 수학적인 사고력을 요구하는 문제이다.

 

 

 

A. Alternately

연속하는 문자열이 있는지 물어보는 문제로, 탐색을 하며 arr[i-1]과 arr[i]를 비교함으로써 해결할 수 있다.

 

 

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	string s; cin >> s;
	string ans = "Yes";
	for (int i=1; i<n; i++) {
	if (s[i-1] == s[i]) ans = "No";
	}
	cout << ans << '\n';
	return 0;
	}

view raw A.cpp hosted with ❤ by GitHub

 

한 번의 탐색으로 해결 가능하므로 시간 복잡도는 $O(N)$이다. ($1 \leq N \leq 100$)

 

 

 

B. Chessboard

column은 인덱스 순으로 a, b, c, d, e, f, g, h에 대응하며

row는 인덱스 순으로 1, 2, 3, 4, 5, 6, 7, 8에 대응하므로 그냥 구현하면 된다.

row는 아래에서 위로 갈수록 인덱스가 증가한다는 점을 주의하자.

 

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	for (int i=8; i>=1; i--) {
	for (int j=1; j<=8; j++) {
	char x; cin >> x;
	if (x == '*') {
	cout << char('a'-1+j);
	cout << i;
	}
	}
	}
	return 0;
	}

view raw B.cpp hosted with ❤ by GitHub

 

2차원 배열을 한 번 탐색하므로 시간 복잡도는 $O(8^2)$이다.

 

 

 

C. Gap Existence

크기가 $2 \leq N \leq 2 \cdot 10^5$인 배열이 주어지며, 배열의 각 원소는 $[-10^9, 10^9]$ 범위의 값을 가지고 있다.

이때, 두 원소의 차이가 정확히 $X$인 쌍이 존재하는지를 묻는 문제이다.

 

두 원소의 차이가 $X$인 쌍이 있는지를 확인할 때 기존 배열의 인덱스는 중요하지 않다.

즉, 원소의 크기가 중요하므로 정렬을 하여 살펴보는 것이 좋다.

사실, 1차원 배열이 나오고 정렬을 해도 상관이 없다면 하는 것이 문제 해석 측면에서 좋다.

 

정렬을 한 뒤에 각 원소를 탐색하며 그 원소와의 차이가 $X$인 원소가 있는지 확인하면 된다.

이를 수행하는 방법은 투 포인터와 이분 탐색 두 가지 방법이 있으며, 각각 $O(N),$ $O(N \cdot \log N)$이 걸린다.

하지만, 정렬을 해야 하기 때문에 전체 시간 복잡도는 $O(N \cdot \log N)$으로 동일하다.

차이가 음수로 나올 수도 있으니 x = abs(x) 처리를 잊지 말자.

 

	// sort & two pointer
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll n, x; cin >> n >> x;
	x = abs(x);
	vector<ll> arr(n);
	for (int i=0; i<n; i++) cin >> arr[i];
	sort(arr.begin(), arr.end());
	int r = 0;
	for (int l=0; l<n; l++) { // check whether exist 'r' that 'arr[r] - arr[i] = x'
	while (r<n-1 && arr[r]-arr[l]<x) r++;
	if (arr[r]-arr[l] == x) {
	cout << "Yes" << '\n';
	return 0;
	}
	}
	cout << "No" << '\n';
	return 0;
	}

view raw C(two pointer).cpp hosted with ❤ by GitHub

 

	// sort & binary search
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll n, x; cin >> n >> x;
	x = abs(x);
	vector<ll> arr(n);
	for (int i=0; i<n; i++) cin >> arr[i];
	sort(arr.begin(), arr.end());
	int r = 0;
	for (int l=0; l<n; l++) { // check whether exist 'r' that 'arr[r] - arr[i] = x'
	ll target = arr[l] + x;
	int r = lower_bound(arr.begin()+l, arr.end(), target) - arr.begin();
	if (r == n) continue;
	if (arr[r] - arr[l] == x) {
	cout << "Yes" << '\n';
	return 0;
	}
	}
	cout << "No" << '\n';
	return 0;
	}

view raw C(binary search).cpp hosted with ❤ by GitHub

 

 

 

D. M<=ab

정수 $1 \leq N, M \leq 10^{12} \ $가 주어지며, 다음 조건을 만족하는 최소의 $X$를 구하면 된다.

$1 \leq a, b \leq N$에 대해, $X = a \times b$로 나타내지며 $X \geq M$를 만족해야 한다.

 

$\small{N^2 < M \ }$인 경우

$X = a \times b$의 최대값은 $a, b$ 둘 다 $N$인 경우이다.

즉, $X = N^2$인 경우이므로 $N^2 < M$이라면 조건을 만족하는 $X$는 존재하지 않는다.

 

$\small{N^2 \geq M \ }$인 경우

$X$의 최대값은 $N^2$이며 $N^2 \geq M$을 만족하므로 $N^2$은 항상 답이 될 수 있다.

일단, 이 경우에는 답은 항상 존재한다는 것이다.

 

답인 $X$를 $X^{*} = a^{*} \times b^{*}$이라고 해보자. ($a^{*} \leq b^{*}$)

우리는 $a$를 고정하면 최적의 $b$를 구할 수 있다.

즉, $a$를 고정하면 $a \times b \geq M$을 만족하는 최적의 $b$를 바로 구할 수 있다.

예를 들어 M=7이고 a=2로 고정하면, 최적의 b는 4라는 것을 바로 알 수 있다.

 

즉, 우리는 $a^{*}$가 될 수 있는 모든 $a$에 대해 탐색하며 최적의 $b$를 확인해 보면 된다.

그렇다면 $a^{*}$의 범위는 어떻게 될까?

 

$N$의 배수와 $M$의 관계에 대해 생각해 보면 $X^{*}$의 상한을 쉽게 파악할 수 있다.

위 그림과 같이 $X \leq M+N$을 만족하는 $X$가 항상 존재하므로 $M \leq X^{*} < M+N$을 항상 만족한다.

따라서, $a^{*}$의 범위는 $1 \leq a^{*} < \sqrt{M+N}$이다.

결론적으로 $1 \leq a < \sqrt{M+N}$ 범위의 $a$에 대해서만 탐색하면 되므로 $O(\sqrt{M})$만에 해결할 수 있다.

 

	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, M; cin >> N >> M;
	// if N²<M, print '-1'.
	if (N<ll(1e6) && N*N<M) {
	cout << -1 << '\n';
	return 0;
	}
	// if N²≥M, X always exists in [M, M+N].
	ll ans = N+M;
	for (ll a=1; a*a<N+M; a++) {
	ll b = (M+a-1)/a;
	if (b <= N) ans = min(ans, a*b);
	}
	cout << (ans == N+M ? -1 : ans) << '\n';
	return 0;
	}

view raw D.cpp hosted with ❤ by GitHub