3090 차이를 최소로 https://www.acmicpc.net/problem/3090
두 문제 모두 좋은문제이다.
1. K번째 수
N*N배열에 $i$행,$j$열에 $i*j$값이 들어간다.
이때 K번째 수를 구하는 문제다.
N이 $10^5$까지 들어오므로 $O(N^2)$으로는 풀 수 없다.
이 문제는 이분 탐색으로 풀 수 있다.
(정확히는 Parametric Search)
어떠한 기준값($w$)을 정했을 때 배열에서 1부터 $w$까지의 개수를 $O(N)$만에 알아낼 수 있다.
이 기준값을 이분 탐색으로 돌리면 $O(N*logN)$만에 해결 가능하다.
#include <cstdio>
int N, K;
int main() {
scanf("%d%d", &N, &K);
int l = 1, r = K;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int n = 1;n <= N;n++) cnt += (mid / n > N ? N : mid / n);
if (cnt < K) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", l);
return 0;
}
| cs |
2. 차이를 최소로
N개의 수열이 주어진다.
수열의 값을 1씩 줄이는 연산을 최대 T만큼 할 수 있을 때
인접한 숫자의 최대차이를 최소로하는 문제이다.
사실 이러한 유형의 문제는 거의 이분탐색으로 바로 보인다.
(최대차이를 최소화하라는 유형)
인접한 숫자의 차이를 기준으로 잡고 이분탐색으로 돌리면 $O(N*logN)$에 해결할 수 있다.
배열의 최대차이를 어떠한 일정한 값으로 만들어주기 위한 방법은 다음과 같다.
오른쪽방향으로 $arr[i + 1]$값이 $arr[i] + diff$보다 큰지 확인하고 크다면 $arr[i+1]$값을 줄여준다.
왼쪽방향으로 $arr[i]$값이 $arr[i+1] + diff$보다 큰지 확인하고 크다면 $arr[i]$값을 줄여준다.
오른쪽방향으로 오른쪽값을 변화시켜주면 이전연산과 다음연산에 영향을 받지 않는다.
왼쪽방향으로 변화시켜주는것 또한 마찬가지이다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M;
int arr[100001];
int tmp[100001];
bool isPossible(int mid) {
int ret = 0;
for (int n = 0;n < N;n++) tmp[n] = arr[n];
for (int n = 0;n < N - 1;n++) {
if (tmp[n] + mid < tmp[n + 1]) {
ret += tmp[n + 1] - (tmp[n] + mid);
tmp[n + 1] = tmp[n] + mid;
}
}
for (int n = N - 1;n > 0;n--) {
if (tmp[n] + mid < tmp[n - 1]) {
ret += tmp[n - 1] - (tmp[n] + mid);
tmp[n - 1] = tmp[n] + mid;
}
}
return ret <= M;
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]);
int l = 0, r = 1e9 + 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (isPossible(mid)) r = mid - 1;
else l = mid + 1;
}
isPossible(l);
for (int n = 0;n < N;n++) printf("%d ", tmp[n]);
return 0;
}
| cs |
2번 차이를 최소로의 문제에서 질문이 있습니다.
답글삭제1. isPossible 함수에서 for문 3개중에 마지막 for문이 하는 역할은 무엇인가요??
2. 이분탐색이 끝난후 다시한번 isPossible(l)을 한번 더 호출하는데 이유를 잘 모르겠습니다.
2번째 for문에서 왼쪽에서 오른쪽 방향으로 수열을 보면서 인접한 두 원소를 비교합니다.
삭제오른쪽값이 왼쪽의 값 + mid보다 클 때 오른쪽 값을 변경해줍니다.
예를들어 mid가 2고 지금 보려는 두 원소가 [4, 7]라면 [4, 6]으로 맞춰주는 거죠. 반면에 두 원소가 [4, 1]이라면
2번째 for문에서는 조건에 해당하지는 않으니 처리하지 않습니다.
이것을 3번째 for문이 조정해주는 역할을 합니다.
3번째 for문은 오른쪽에서 왼쪽방향으로 가면서 값을 왼쪽값을 변경해줍니다.
isPossible(l)을 호출하는 이유는 우선 l이 이분탐색의 결과로 차이를 최소로하는 최솟값입니다.
삭제이함수가 호출된 후의 tmp는 차이를 최소로 하는 변경된 수열이기 때문에 한번 돌려주고 출력을 하게했습니다.
이미 함수내에 변경된 수열을 출력하는 코드가있어 그냥 재사용한겁니다..