[CF 1667A] Make it Increasing

[CF 1667A] Make it Increasing - 1300

 

Problem - A - Codeforces

 

문제 설명

길이가 n인 배열 a가 주어지고, 모든 원소가 0인 길이가 n인 배열 b가 있다. 이때 $b_{i}$에서 $a_{i}$를 원하는 만큼 더하거나 빼는 연산을 할 수 있다. 배열 b를 중복 없이 증가하는 수열로 만들고자 할 때 필요한 최소 연산의 수를 구하시오.

문제 풀이

1. N의 크기가 5000밖에 되지 않기 때문에 $N^2$풀이를 생각해볼 수 있다.
2. $N^2$이라면 고정된 i에 대한 최솟값을 $N$만에 구하고, i를 [1, N]에 대해 다 돌려보면 된다.
3. 고정된 i의 위치의 값은 0이고, 그 양 옆 범위인 [1,i-1], [i+1,N]의 범위만 조작하면 된다. 그리고 양 옆 범위는 대칭적인 형태를 띨 것이라 예상할 수 있다.
4. [1,i-1]을 생각해보자. $b_i$=0이고, 나는 $b_1,b_2,b_3...b_{i-1}$값만 조작할 것이다.
5. i에서 가장 가까운 $b_{i-1}$부터 보자. 이 값에는 0보다는 작으면서 가장 큰 수(절대값이 가장 큰 수)가 되도록만 조작해주면 된다. 따라서 $b_{i-1}$는 연산이 1번 소요된다.
6. $b_{i-2}$를 보자. 얘는 $b_{i-1}$보다는 작으면서 가장 큰 수가 되도록 $a_{i-2}$를 빼주면 된다. 그 횟수는 $b_{i-1}$/$a_{i-2}$ + 1 이다.
7. 같은 시행을 $i-3,i-4,...3,2,1$에 대해서 시행한다.
8. [i+1,N]도 똑같이 시행한다.
9. 이 횟수를 모두 다 더하면 i를 고정했을 때의 값이 나온다. 이를 [1,N]에 대해서 모두 시행한다.

소스 코드

const int SIZE= 5009;
int a[SIZE];

int main(){
    int n;  scanf("%d",&n);
    for(int i=1 ; i<=n ; i++){
      scanf("%d",&a[i]);
    }

    ll ans = 1LL<<61;
    for(int i=1 ; i<=n ; i++){
      ll cur = 0;
      for(ll j=i-1,last=0 ; j>=1 ; j--){
        ll k = last / a[j] + 1;
        cur += k;
        last = k * a[j];
      }
      for(ll j=i+1,last=0 ; j<=n ; j++){
        ll k = last / a[j] + 1;
        cur += k;
        last = k * a[j]; 
      }
      ans = min(ans,cur);
    }
    printf("%lld\n",ans);
}