문제 93
증가 수열 만들기
길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
수열 $A$에 다음 연산을 $0$회 이상 수행하여 증가 수열로 만들 수 있는지 판별하라.
- $1 \le i<j \le N$인 두 정수 $i$, $j$를 선택한 뒤, $A_i$에 $1$을 더하고 $A_j$에서 $1$을 뺀다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$
출력
첫 번째 줄에 수열 $A$를 증가 수열로 만들 수 있다면 Yes를, 그렇지 않다면 No를 출력한다.
예제 입력 1
3 1 1 4
예제 출력 1
Yes
예제 입력 2
3 1 1 2
예제 출력 2
No
예제 입력 3
5 1 1 2 6 5
예제 출력 3
Yes
노트
길이가 $N$인 수열 $A$가 증가 수열이라는 것은 $1 \le i<N$인 모든 정수 $i$에 대하여 $A_i<A_{i+1}$을 만족한다는 뜻이다.
공식 해설
도달 가능성은 접두사 합으로 결정된다
연산은 오른쪽의 값을 왼쪽으로 옮기므로 전체 합을 유지하면서 모든 접두사 합을 감소시키지 않는다. 따라서 목표 수열 $B$로 바꿀 수 있으려면
\[
\sum_{i=1}^{k}B_i\ge\sum_{i=1}^{k}A_i\quad(1\le k\le N)
\]
이고 전체 합은 같아야 한다.
이 조건은 충분하기도 하다. 두 접두사 합의 차를 $d_k$라 두면 $d_0=d_N=0$, $d_k\ge0$이다. $k=N-1$부터 $1$까지 차례로 $k+1$번 원소에서 $k$번 원소로 $d_k$를 옮기면 최종값은 $A_i+d_i-d_{i-1}=B_i$가 된다.
접두사 합이 가장 큰 증가 수열 하나만 검사하기
증가 수열에서 $i$번째 값에 $i-1$을 빼면 감소하지 않는 정수 수열이 된다. 이 수열의 최댓값과 최솟값 차가 $2$ 이상이면 마지막 최솟값에 $1$을 더하고 첫 최댓값에서 $1$을 빼자.
변경 후에도 감소하지 않는 순서를 유지한다. 또한 뒤의 값을 앞으로 옮겼으므로 어느 접두사 합도 줄지 않는다. 이를 반복하면 모든 값의 차가 최대 $1$인 수열에 도달한다. 다시 $i-1$을 더하면, 같은 전체 합을 가진 증가 수열 중 모든 접두사 합이 최대인 형태를 얻는다.
전체 합을 $T$라 하고
\[
C=T-\frac{N(N-1)}2=Nq+r,\qquad 0\le r<N
\]
로 나타내자. 그 최적의 목표 수열은
\[
B_i=q+i-1+[i>N-r]
\]
이다. 즉 $q,q+1,\cdots,q+N-1$에서 마지막 $r$개 원소만 $1$ 더한다. $[P]$는 참일 때 $1$, 거짓일 때 $0$이다.
이 수열은 엄격히 증가하고 합이 $T$이다. 다른 어떤 증가 수열도 이보다 접두사 합이 클 수 없으므로, 이 수열에 대해서만 처음의 접두사 조건을 검사하면 된다. 모두 만족하면 Yes, 하나라도 작으면 No이다.
구현할 때의 나눗셈
$C$가 음수일 수도 있으므로 $q=\lfloor C/N\rfloor$는 내림 나눗셈이어야 한다. 또는 먼저 $T<N(N+1)/2$이면 No로 처리하면 남은 경우에는 $C\ge0$이다. 이 조기 판정은 첫 원소를 감소시킬 수 없고 $A_1\ge1$이어서 목표 증가 수열의 합이 적어도 $1+2+\cdots+N$이어야 한다는 데서 나온다.
전체 합 $T$와 $N(N-1)/2$는 원소 하나보다 클 수 있으므로 누적합과 곱도 정확히 계산해야 한다. 입력을 저장한 뒤 목표 수열을 만들며 접두사 합을 비교하면 시간복잡도는 $O(N)$, 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
수열과 누적합을 long long으로 저장하고 1LL * N * (N - 1) / 2처럼 곱셈 전부터 형을 넓힌다. 전체 합이 $N(N+1)/2$보다 작으면 먼저 제외하면 남은 나눗셈은 음수가 아니다. 이를 제외하지 않는 구현에서는 C++의 음수 정수 나눗셈이 내림과 다르므로 몫과 나머지를 보정한다.
C 구현
합과 N*(N-1)/2는 long long으로 계산한다. T < N*(N+1)/2이면 먼저 No로 처리하면 나머지의 C가 음수가 아니다. 그 뒤 q=C/N, r=C%N으로 목표 수열과 접두사 합을 만든다.
앞의 최소 합 검사를 통과한 경우 t는 전체 합, a는 입력 배열이다. 목표 배열을 별도로 만들지 않고 접두사 합을 비교한다.
long long c = t - 1LL * n * (n - 1) / 2;
long long q = c / n, r = c % n;
long long original = 0, target = 0;
int ok = 1;
for (int i = 0; i < n; i++) {
original += a[i];
target += q + i + (i >= n - r);
if (target < original) ok = 0;
}Python 구현
q,r=divmod(C,N)은 C가 음수여도 내림 나눗셈을 제공한다. 0-based i의 목표는 q+i+(i>=N-r)이다. 원래·목표 접두사 합을 정수로 비교하며 목표 전체 배열은 필요 없다.
a의 길이가 n이다. divmod의 나머지는 음수 c에서도 항상 $0$ 이상이다.
c = sum(a) - n * (n - 1) // 2
q, r = divmod(c, n)
original = target = 0
ok = True
for i, x in enumerate(a):
original += x
target += q + i + (i >= n - r)
if target < original:
ok = FalseJava 구현
합과 삼각수는 long으로 계산한다. 조기 판정 없이 음수 C를 허용한다면 Math.floorDiv, Math.floorMod를 사용한다. 일반 /와 %는 음수에서 공통 풀이의 q,r과 다르다.
t는 전체 합, a는 입력 배열이다. 내림 나눗셈을 사용하면 음수인 경우도 같은 식으로 처리한다.
long c = t - 1L * n * (n - 1) / 2;
long q = Math.floorDiv(c, n), r = Math.floorMod(c, n);
long original = 0, target = 0;
boolean ok = true;
for (int i = 0; i < n; i++) {
original += a[i];
target += q + i + (i >= n - r ? 1 : 0);
if (target < original) ok = false;
}Rust 구현
i64로 합과 삼각수를 구한다. 음수 C를 그대로 처리할 때는 div_euclid와 rem_euclid로 0<=r<N을 유지한다. 또는 먼저 최소 양수 증가 수열 합을 검사해 C>=0인 경우만 처리한다.
위치의 비교도 부호 있는 정수로 맞추고, 목표 배열 대신 두 누적합만 관리한다.
let n = a.len() as i64;
let c = a.iter().sum::<i64>() - n * (n - 1) / 2;
let q = c.div_euclid(n);
let r = c.rem_euclid(n);
let (mut original, mut target) = (0i64, 0i64);
let mut ok = true;
for (i, &x) in a.iter().enumerate() {
original += x;
target += q + i as i64 + if i as i64 >= n - r { 1 } else { 0 };
if target < original { ok = false; }
}JavaScript 구현
합은 최대 $10^{14}$, $N(N-1)/2$는 $5\cdot10^9$ 미만이므로 Number 정수 연산으로 정확하다. $C$가 음수일 때도 몫은 내림이어야 하므로 Math.floor(c / n)를 사용하고 나머지는 c - q * n으로 구한다.
const total = a.reduce((s, x) => s + x, 0);
const c = total - n * (n - 1) / 2;
const q = Math.floor(c / n);
const r = c - q * n;
let original = 0, target = 0, ok = true;
for (let i = 0; i < n; i++) {
original += a[i];
target += q + i + (i >= n - r ? 1 : 0);
if (target < original) ok = false;
}
console.log(ok ? 'Yes' : 'No');Math.trunc나 $32$비트 변환으로 몫을 구하면 음수의 내림과 큰 값에서 틀릴 수 있다. 목표 원소는 차례로 계산하므로 목표 배열을 따로 만들 필요가 없다.