중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터

ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 4. 00:21

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II)

$D P_{i} :=$ $i$ 번째 원소로 끝나는 LIS 로 정의하면,

$D P_{i} = max_{A_{j} < A_{i}} D P_{j} + 1$ 로 점화식을 세울 수 있습니다.

초기값은 $D P_{i} = 1$ 이고, 문제의 답은 $max_{1 \leq i \leq N} D P_{i}$ 입니다.

int arr[1020], dp[1020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j <= i; j++){
			if (arr[j] >= arr[i]){ continue; }
			dp[i] = max(dp[i], dp[j]+1);
		}
	}
	cout << *max_element(dp+1, dp+n+1);
}

B. [2003] 수들의 합 2 (Silver III)

두 포인터 p1과 p2를 놓고, [p1, p2) 구간의 합을 저장하면서 포인터를 잘 움직여봅시다.

만약 현재 합이 $M$ 이하라면 p2를 오른쪽으로 옮겨줘야 하고,

그렇지 않으면 p1을 오른쪽으로 옮겨줘야 합니다.

문제의 답은 합이 정확히 $M$ 이 된 횟수이며, 시간복잡도는 $O (N)$ 입니다.

+ $A_{i}$ 가 자연수이기 때문에 가능합니다. 그냥 정수라면 사용할 수 없습니다.

1. [1920] 수 찾기 (Silver IV)

수열 $A$ 와 찾는 수 $X$ 가 주어질 때, 이를 이진 탐색으로 찾아주면 됩니다.

lower_bound를 사용한다면 $X$ 이상인 위치를 찾아줄테니, 그 위치에 있는 수가 $X$ 인지 확인해주면 됩니다.

주의할 점: $X$ 가 수열의 모든 원소보다 크다면 lower_bound가 $N + 1$ 번 위치를 가리키게 됩니다.

근데 이걸 생각 못한 채로 그냥 Indexing을 해도 웬만해서는 답이 잘 나오지만...

[-6, -4, -2]에서 0을 찾으려 하는 순간 잘못된 답이 나오는 걸 볼 수 있습니다.

int arr[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	int q; cin >> q; while (q--){
		int x; cin >> x;
		auto idx = lower_bound(arr+1, arr+n+1, x) - arr;
		if (idx > n){ cout << 0 << endl; continue; }
		cout << (arr[idx] == x) << endl;
	}
}

STL이 존재하는데에는 이유가 있습니다. 신나게 set을 박아주면 됩니다.

set<int> s;

void Main(){
	int n; cin >> n;
	while (n--){ int x; cin >> x; s.insert(x); }
	int q; cin >> q;
	while (q--){ int x; cin >> x; cout << s.count(x) << endl; }
}

2. [1654] 랜선 자르기 (Silver III)

문제의 답이 $X$ 라고 하면, $X$ 이하의 길이를 가지는 랜선은 만들 수 있지만, $X$ 초과의 길이를 가지는 랜선은 만들 수 없기에, 이 문제를 파라메트릭 서치로 풀 수 있는 길을 만들어줍니다.

그러니, 길이가 $x$ 인 랜선을 $N$ 개 이상 만들 수 있는지 판별하는 함수를 만들어봅시다.

어떤 랜선 $a$ 에 대해, 길이가 $x$ 인 랜선은 $⌊ a / x ⌋$ 개 만들 수 있습니다.

그러니, 랜선의 배열을 $A$ 라고 하면 길이가 $x$ 인 랜선은 $\sum_{i = 1}^{K} ⌊ A_{i} / x ⌋$ 개 만들 수 있습니다.

이 값이 $N$ 이상이라면 더 긴 길이를 시도해보고, 그렇지 않다면 더 짧은 길이를 시도해보면 됩니다.

int arr[10020];

void Main(){
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 1, ed = 1e10, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += arr[i] / mid; }
		if (res >= k){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

3. [12015] 가장 긴 증가하는 부분 수열 2 (Gold II)

A. [11053] 가장 긴 증가하는 부분 수열 의 점화식을 그대로 가지고 올 수는 없는 문제입니다.

그러니, DP를 참신하게 세워봅시다.

$D P_{i} :=$ 길이가 $i$ 인 LIS의 마지막 원소 중 최솟값

도대체 이걸로 뭘 하나 싶겠지만, 이러면 $D P_{i} < D P_{i + 1}$ 이라는 재밌는 사실이 하나 나오게 됩니다.

그리고 저 사실이 큰 역할을 해줍니다.

$D P_{k} < A_{i}$ 인 가장 큰 $k$ 를 찾았다면, 이는 길이 $k + 1$ 의 LIS를 만들 수 있다는 것이며, 더 나아가 길이 $k + 2$ 의 LIS는 만들 수 없다는 소리가 되기 때문입니다.

그러니, $D P_{k} < A_{i}$ 인 가장 큰 $k$ 를 찾은 뒤, $D P_{k + 1}$ 을 이에 맞게 업데이트해주면 됩니다.

만약 길이 $k + 1$ 의 LIS가 없었다면, 답의 길이도 1 증가시켜야 합니다.

실제 구현에서는 구현의 편의를 위해 $D P_{k} \geq A_{i}$ 인 가장 작은 $k$ 를 찾은 뒤 $D P_{k}$ 를 업데이트해줍니다. 이게 위 방식과 동일함은 $D P_{k - 1} < A_{i} \leq D P_{k}$ 를 생각해보면 자명합니다.

int arr[1000020], lis[1000020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << cnt;
}

4. [10816] 숫자 카드 2 (Silver IV)

"1. [1920] 수 찾기" 문제의 강화판입니다.

이제는 개수를 세야 하는데, 개수는 upper_bound의 위치 - lower_bound의 위치 로 구할 수 있습니다.

+ equal_range는 lower_bound와 upper_bound의 위치를 동시에 return합니다.

이름이 equal_range인 이유는, [lower, upper) 구간에 target과 동일한 값이 들어있기 때문입니다.

int arr[500020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	int q; cin >> q; while (q--){
		int x; cin >> x;
		auto p = equal_range(arr+1, arr+n+1, x);
		cout << p.sc - p.fr << ' ';
	}
}

"1. [1920] 수 찾기"에서 set을 박은 걸 기억하나요?

여기서는 { x: count }의 형태로 map을 박으면 됩니다.

map<int, int> mp;

void Main(){
	int n; cin >> n;
	while (n--){ int x; cin >> x; mp[x] += 1; }
	int q; cin >> q;
	while (q--){ int x; cin >> x; cout << mp[x] << ' '; }
}

5. [3020] 개똥벌레 (Gold V)

밑에서 올라오는 장애물과 위에서 내려오는 장애물을 따로 처리해봅시다.

높이 $h$ 에서 날아갈 때 부딪히는 장애물은 밑에서 올라오는 장애물 중 $h$ 위로 올라가는 장애물의 개수 + 위에서 내려오는 장애물 중 $h$ 밑으로 내려가는 장애물의 개수 가 됩니다.

이 2개 모두 이진 탐색을 사용하여 구해줄 수 있습니다.

이를 모든 높이에서 돌려준 뒤, 파괴해야 하는 장애물의 최솟값과 위치를 출력해주면 됩니다.

시간복잡도는 $O (N + H \log N)$ 입니다.

vector<int> v1, v2;

void Main(){
	int n, m; cin >> m >> n;
	for (int i = 1; i <= m; i++){
		int x; cin >> x;
		if (i&1){ v1.push_back(x); }
		else{ v2.push_back(n-x+1); }
	}
	sort(all(v1)); sort(all(v2));
	int ans = 1e9, cnt = 0;
	for (int i = 1; i <= n; i++){
		int c1 = v1.end() - lower_bound(all(v1), i);
		int c2 = upper_bound(all(v2), i) - v2.begin();
		int res = c1+c2;
		if (ans > res){ ans = res; cnt = 0; }
		if (ans == res){ cnt += 1; }
	}
	cout << ans << ' ' << cnt << endl;
}

(풀이 1에서 이어집니다.)

그런데 굳이 이진 탐색을 써야 할까요?

누적합을 사용해서 위에서 나온 2개의 경우를 계산해둘 수도 있다.

이제 시간복잡도는 $O (N + H)$ 가 되었습니다.

int c1[500020], c2[500020];

void Main(){
	int n, m; cin >> m >> n;
	for (int i = 1; i <= m; i++){
		int x; cin >> x;
		if (i&1){ c1[x] += 1; }
		else{ c2[n-x+1] += 1; }
	}
	for (int i = n; i >= 1; i--){ c1[i] += c1[i+1]; }
	for (int i = 1; i <= n; i++){ c2[i] += c2[i-1]; }
	int ans = 1e9, cnt = 0;
	for (int i = 1; i <= n; i++){
		int res = c1[i] + c2[i];
		if (ans > res){ ans = res; cnt = 0; }
		if (ans == res){ cnt += 1; }
	}
	cout << ans << ' ' << cnt << endl;
}

사실 누적합을 이렇게 써서 풀 수도 있습니다.

밑에서 올라오는 건 [1, h] 구간에 장애물이 생기는 거고, 위에서 내려오는 건 [h, H] 구간에 장애물이 생기는 것이 됩니다.

그리고 [st, ed] 구간의 장애물은 $A_{s t}$ 에 1을 더한 뒤 $A_{e d + 1}$ 에 1을 빼고, 나중에 누적합을 넣는 방식으로 구현할 수 있습니다.

시간복잡도는 $O (N + H)$ 가 됩니다.

int prf[500020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int pos; cin >> pos;
		if (i&1){ prf[1] += 1; prf[pos+1] -= 1; }
		else{ prf[m-pos+1] += 1; prf[m+1] -= 1; }
	}
	for (int i = 1; i <= m; i++){ prf[i] += prf[i-1]; }
	int mn = 1e9, mnc = 0;
	for (int i = 1; i <= m; i++){
		if (mn > prf[i]){ mn = prf[i]; mnc = 0; }
		if (mn == prf[i]){ mnc += 1; }
	}
	cout << mn << ' ' << mnc;
}

6. [2792] 보석 상자 (Silver II)

질투심이 낮아질수록 보석을 받는 학생 수가 늘어나므로, 질투심을 기준으로 Parametric Search를 돌려봅시다.

질투심이 $X$ 이하가 되도록 $A$ 개의 보석을 나누면, 최소 $⌈ A / X ⌉$ 명의 학생에게 보석을 나눠줘야 합니다.

그러니 이를 모든 종류의 보석에 돌려줬을 때의 결과 $\sum_{i = 1}^{N} ⌈ A_{i} / X ⌉$ 를 계산한 뒤, 이게 $N$ 이하라면 질투심을 더 낮춰보고, 아니면 질투심을 더 높여주면 됩니다.

시간복잡도는 $O (N \log 2 \cdot 10^{9})$ 가 됩니다.

ll arr[300020];

void Main(){
	ll n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 1, ed = 2e9, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += (arr[i]+mid-1)/mid; }
		if (res <= m){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	cout << ans;
}

7. [2512] 예산 (Silver III)

상한을 $X$ 라고 합시다. 자명하게, 상한을 낮게 잡을 수록 배정 금액이 낮아집니다.

그러니 파라메트릭 서치로 잘 풀어주면 될 것 같습니다.

상한이 $X$ 일 때 배정되는 예산은 다음과 같이 구할 수 있습니다. $\sum_{i = 1}^{N} min (A_{i}, X)$

이 예산이 총 예산을 넘는다면 상한을 작게, 아니라면 상한을 크게 잡아주면 됩니다.

ll arr[10020];

void Main(){
	int n; cin >> n; ll mx = 0;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; mx = max(mx, arr[i]); }
	ll m; cin >> m;
	ll st = 1, ed = mx, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += min(arr[i], mid); }
		if (res <= m){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

8. [1072] 게임 (Silver III)

승률이 한 번 바뀐 뒤로는 더 오르거나 / 가만히 있기 때문에 안 바뀐 상태로 돌아가는 경우는 없습니다.

그러니 파라메트릭 서치를 사용해서 추가 플레이 횟수를 구해봅시다.

$P$ 회 게임을 더 한 뒤의 승률은 $⌊ 100 \cdot \frac{X + P}{Y + P} ⌋ %$ 가 됩니다. 그러니 이 값이 원래 있던 Z와 다른지 판별해주면 됩니다.

$[1, 10^{1} 2]$ 구간에서 돌려주면 답이 잘 나옵니다.

아무리 돌려도 Z가 변하지 않는다면 -1을 출력해야 함에 주의하세요.

void Main(){
	ll x, y; cin >> x >> y;
	ll z = 100*y / x;
	ll st = 1, ed = 1e12, ans = -1;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 100 * (y+mid)/(x+mid);
		if (z != res){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	cout << ans;
}

9. [2805] 나무 자르기 (Silver III)

높이가 낮아질수록 가져갈 수 있는 나무의 길이는 길어집니다.

그러니 최적의 높이를 Parametric Search로 찾아봅시다.

높이를 $X$ 미터로 설정했을 때 가져갈 수 있는 나무의 길이는 $\sum_{i = 1}^{n} max (A_{i}, 0)$ 입니다.

그러니, 저 길이가 목표인 $M$ 보다 크거나 같다면 더 높은 높이를, 아니면 더 낮은 높이를 시도해보면 됩니다.

시간복잡도는 $O (N \log 10^{9})$ 입니다.

ll arr[1000020];

void Main(){
	int n; ll m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll st = 0, ed = 1e9, ans = 0;
	while (st <= ed){
		ll mid = st+ed >> 1;
		ll res = 0;
		for (int i = 1; i <= n; i++){ res += max(arr[i]-mid, 0LL); }
		if (res >= m){ st = mid+1; ans = mid; } else{ ed = mid-1; }
	}
	cout << ans;
}

10. [2613] 숫자구슬 (Gold II)

그룹의 합의 최댓값이 클 수록 그룹의 개수는 작아질테니, 그룹의 합의 상한선을 기준으로 Parametric Search를 돌려봅시다.

만약 그룹의 합이 $X$ 를 넘지 못한다면, 어떻게 합쳐야 할까요?

다양한 방법이 있겠지만, 1번 그룹만을 보면 '되는대로 합친다'가 답이 됩니다.

그럼 이를 토대로 2번 그룹을 보면 역시 '되는대로 합치는' 게 최적이고,

이런 식으로 모든 그룹에 대해 "합이 넘지 않는 동안 계속 합친다"를 해주는 게 최적입니다.

이런 식으로 그룹을 합쳤을 때 $M$ 개 이하의 그룹이 만들어졌다면 더 작은 최댓값을 탐색하고, 아니면 더 큰 최댓값을 탐색해보면 됩니다.

주의할 점으로는, 그룹의 개수가 정확히 $M$ 개여야 하지만, 위 방식으로는 정확히 $M$ 개가 아닌 경우가 만들어질 수도 있습니다.

이 경우, 그냥 $M$ 개가 될 때까지 마음대로 더 잘라주면 됩니다.

+ 마음대로 더 자르다가 최댓값이 더 작아지면 어떡해야 하죠?

만약 최댓값이 더 작아질 수 있다면 그걸 Parametric Search에서 잡아냈을 테니, 그런 경우는 없습니다.

int arr[320];

void Main(){
	int n, m; cin >> n >> m; int mx = 0;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; mx = max(mx, arr[i]); }
	int st = mx, ed = 30000, ans = 0;
	while (st <= ed){
		int mid = st+ed >> 1;
		int sum = 0, res = 1;
		for (int i = 1; i <= n; i++){
			sum += arr[i];
			if (sum > mid){ sum = arr[i]; res += 1; }
		}
		if (res <= m){ ed = mid-1; ans = mid; } else{ st = mid+1; }
	}
	vector<int> anv;
	int sum = 0, ptr = 1;
	for (int i = 1; i <= n; i++){
		sum += arr[i];
		if (sum > ans){ anv.push_back(i-ptr); sum = arr[i]; ptr = i; }
	}
	anv.push_back(n+1-ptr);
	cout << ans << endl;
	int vl = anv.size();
	for (int& x : anv){
		while (vl < m){
			if (x == 1){ break; }
			cout << 1 << ' ';
			x -= 1; vl += 1;
		}
		cout << x << ' ';
	}
}

11. [3745] 오름세 (Gold III)

오름세의 정의를 생각해보면, Increasing Sequence와 동일함을 알 수 있습니다.

그 중 가장 긴 (Longest) 걸 찾아야 하니, 정직한 LIS 문제임을 알 수 있습니다.

int arr[100020], lis[100020];

void Main(){
	int n; while (cin >> n){
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		int cnt = 0;
		for (int i = 1; i <= n; i++){
			auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
			if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
		}
		cout << cnt << endl;
		for (int i = 0; i < cnt; i++){ lis[i] = 0; }
	}
}

12. [2352] 반도체 설계 (Gold III)

꼬이지 않도록 연결한다는 건, $i < j$ 일 때 $A_{i} < A_{j}$ 라는 것입니다.

그러니, 이 개수가 최대라는 건 $i_{1} < i_{2} < \dots < i_{k}$ 일 때 $A_{i_{1}} < A_{i_{2}} < \dots < A_{i_{k}}$ 인 $k$ 를 최대화해야 한다는 것입니다.

뭔가 익숙하지 않나요? 방금 설명한 문제는 LIS 문제와 동일합니다.

그러니, 꼬이지 않는 연결선의 개수 = LIS의 길이가 됩니다.

$N \leq 40000$ 이니 $O (N \log N)$ 으로 구해줘야 합니다.

int arr[40020], lis[40020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << cnt;
}

13. [1365] 꼬인 전깃줄 (Gold III)

자르는 전선의 개수를 최소화하는 것과 꼬이지 않는 전깃줄의 개수를 최대화하는 건 동일하므로, 꼬이지 않는 전깃줄의 개수를 세봅시다.

그런데 꼬이지 않는 전깃줄의 개수는 12. [2352] 반도체 설계 문제에서 이미 구해봤습니다.

즉, LIS의 길이가 됩니다.

이번에는 자르는 전선의 개수이니, N - (LIS의 길이)를 출력해주면 됩니다.

$N \leq 100000$ 이니, $O (N \log N)$ 으로 풀어주면 됩니다.

int arr[100020], lis[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		auto idx = lower_bound(lis, lis+cnt, arr[i]) - lis;
		if (idx == cnt){ cnt += 1; } lis[idx] = arr[i];
	}
	cout << n-cnt;
}

14. [10025] 게으른 백곰 (Silver IV)

$[x - K, x + K]$ 구간에서 $[x + 1 - K, x + 1 + K]$ 구간으로 이동할 때는 $A_{x + 1 + K}$ 를 더한 뒤 $A_{x - K}$ 를 빼주면 됩니다.

그러니 우선 $[- 2 K, 0]$ 구간에서의 얼음 개수를 구한 뒤, 이를 오른쪽으로 1칸씩 밀어주면서 최댓값을 구해주면 됩니다.

시간복잡도는 $O (X = 10^{6})$ 입니다.

ll arr[1000020];

void Main(){
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		arr[y] += x;
	}
	ll ans = 0, res = 0;
	for (int i = 0; i <= 1000000; i++){
		int j = i - 2*k - 1;
		if (j >= 0) res -= arr[j];
		res += arr[i];
		ans = max(ans, res);
	}
	cout << ans;
}

15. [2467] 용액 (Gold V)

입력으로 들어오는 $A$ 는 오름차순으로 정렬되어있습니다.

그러니 바로 두 포인터를 p1 = 1에, p2 = N에 놓고 시작해봅시다.

만약 $A_{p 1}$ 과 $A_{p 2}$ 의 부호가 같다면, $| A_{p 1} + A_{p 1 + 1} |$ 과 $| A_{p 2 - 1} + A_{p 2} |$ 중 더 작은 걸 찾고 끝내면 됩니다.

그렇지 않다면, $A_{p 1} \leq 0 \leq A_{p 2}$ 입니다.

만약 $| A_{p 1} | < | A_{p 2} |$ 라면 p2를 움직여주면 되고 (p2 -= 1),

그렇지 않다면 p1을 움직여주면 됩니다 (p1 += 1).

답은 두 포인터를 이동하면서 만난 모든 $| A_{p 1} + A_{p 2} |$ 중 최솟값이고, 이 때의 $A_{p 1}, A_{p 2}$ 를 출력해주면 됩니다.

시간복잡도는 $O (N)$ 입니다.

ll arr[100020];

ll ans = 1e15, x=0, y=0;
void f(int p1, int p2){
	ll res = abs(arr[p1] + arr[p2]);
	if (ans > res){ ans = res; x = arr[p1]; y = arr[p2]; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int p1 = 1, p2 = n;
	while (p1 < p2){
		f(p1, p2);
		if (arr[p1] > 0){ f(p1, p1+1); break; }
		if (arr[p2] < 0){ f(p2-1, p2); break; }
		if (abs(arr[p1]) <= abs(arr[p2])){ p2 -= 1; }
		else{ p1 += 1; }
	}
	cout << x << ' ' << y << endl;
}

사실 이 문제는 이진 탐색만으로도 풀 수 있습니다.

1번 용액 $x$ 를 고정한다면, 2번 용액은 $- x$ 에 가장 가까운 값으로 선택해야 하므로,

$- x$ 를 기준으로 이진 탐색을 해줘서 $- x$ 미만의 수 중 가장 큰 수와 $- x$ 이상의 수 중 가장 작은 수 2개를 찾을 수 있고, 둘 중 더 좋은 해를 선택해주면 됩니다.

시간복잡도는 $O (N \log N)$ 입니다.

ll arr[100020];

ll ans = 1e15, x=0, y=0;
void f(int p1, int p2){
	ll res = abs(arr[p1] + arr[p2]);
	if (ans > res){ ans = res; x = arr[p1]; y = arr[p2]; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		int j1 = lower_bound(arr+1, arr+n+1, -arr[i]) - arr;
		int j2 = j1 - 1;
		if (j1 == i){ j1 += 1; } if (j2 == i){ j2 -= 1; }
		if (j1 <= n){ f(i, j1); }
		if (1 <= j2){ f(i, j2); }
	}
	if (x > y){ swap(x, y); }
	cout << x << ' ' << y;
}

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

중급반 6주차 풀이 - 최단경로 (BFS, 다익스트라) (0)	2022.05.18
중급반 5주차 풀이 - DFS, BFS, 백트래킹 (0)	2022.05.12
중급반 4주차 풀이 - 냅색, 구간 DP (0)	2022.05.04
중급반 2주차 풀이 - 그리디, DP, 분할 정복 (0)	2022.05.02
중급반 1주차 풀이 - Brute Force (0)	2022.04.30

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

인기포스트

ABOUT ME

hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II)

B. [2003] 수들의 합 2 (Silver III)

1. [1920] 수 찾기 (Silver IV)

2. [1654] 랜선 자르기 (Silver III)

3. [12015] 가장 긴 증가하는 부분 수열 2 (Gold II)

4. [10816] 숫자 카드 2 (Silver IV)

5. [3020] 개똥벌레 (Gold V)

6. [2792] 보석 상자 (Silver II)

7. [2512] 예산 (Silver III)

8. [1072] 게임 (Silver III)

9. [2805] 나무 자르기 (Silver III)

10. [2613] 숫자구슬 (Gold II)

11. [3745] 오름세 (Gold III)

12. [2352] 반도체 설계 (Gold III)

13. [1365] 꼬인 전깃줄 (Gold III)

14. [10025] 게으른 백곰 (Silver IV)

15. [2467] 용액 (Gold V)

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

인기포스트

ABOUT ME

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II)

B. [2003] 수들의 합 2 (Silver III)

1. [1920] 수 찾기 (Silver IV)

2. [1654] 랜선 자르기 (Silver III)

3. [12015] 가장 긴 증가하는 부분 수열 2 (Gold II)

4. [10816] 숫자 카드 2 (Silver IV)

5. [3020] 개똥벌레 (Gold V)

6. [2792] 보석 상자 (Silver II)

7. [2512] 예산 (Silver III)

8. [1072] 게임 (Silver III)

9. [2805] 나무 자르기 (Silver III)

10. [2613] 숫자구슬 (Gold II)

11. [3745] 오름세 (Gold III)

12. [2352] 반도체 설계 (Gold III)

13. [1365] 꼬인 전깃줄 (Gold III)

14. [10025] 게으른 백곰 (Silver IV)

15. [2467] 용액 (Gold V)

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역