[CF 1082E] Increasing Frequency

[CF 1082E] Increasing Frequency - 2000

문제 설명 : 

배열 내의 임의의 구간에 대해서 임의의 수를 더하거나 빼는 연산을 할 수 있다. 이 연산을 수행한 뒤 c가 가장 많이 등장할 수 있는 빈도수를 구하는 문제이다.

풀이 : 

두 가지 풀이가 있다. 하나는 dp를 이용한 풀이이고 다른 하나는 그리디를 이용한 풀이인데, 그리디를 이용한 풀이가 짧고 간결하지만 아이디어적이라서 떠올리기가 쉽지는 않다. 그래서 dp를 이용한 풀이를 먼저 설명하겠다.

cnt(l,r,x)를 구간 [l,r]에서 x의 등장 빈도수라고 정의하자. 그러면 이 문제는 연산을 수행한 뒤에 cnt(l,r,c)의 최대를 구하는 문제가 된다. 여기서 나는 연산을 수행할 것이기에 c가 아닌 수 d에 특정 수를 더함으로써 c로 만들 수 있다. 즉 최종정답 ans는 기존배열 [1,n]에서 c의 빈도수 + [l,r]구간에서 d의 빈도수 - [l,r]구간에서 c의 빈도수이고 수식으로 표현하면 

ans = cnt(1,n,c) + ( cnt(l,r,d) - cnt(l,r,c) ) 로 쓸 수 있다. 

여기서 cnt(1,n,c)는 고정된 값이므로 내가 고려해야 할 것은 cnt(l,r,d) - cnt(l,r,c)의 최대값을 구하는 것이다. 이를 계산하기 위해서 나는 특정 d값을 고정시켜놓은 뒤에 전체 구간을 돌아보면서 그 값을 구할 것이다. 이렇게 하면 시간복잡도는 입력 값의 최대 범위 50만 * 배열의 크기 50만이므로 시간이 터지게 된다. 따라서 전체 구간을 돌아볼 때, 모든 구간을 살펴보는게 아닌, 고정된 d값이 나온 인덱스에 대해서만 살펴보면 시간을 줄일 수 있다. 그래서 나는 처음 배열 값을 입력받을 때부터 그 값이 나타난 인덱스를 vector에 저장해놓을 것이다. 그리고 고정된 d값이 있을 때 d가 나타난 인덱스에 대해서만 살펴본다. 여기서 cnt(l,r,x) = cnt(1,r,x)-cnt(1,l-1,x)로 표현할 수 있다. 그러므로 cnt(l,r,d) - cnt(l,r,c)의 최대값을 구하기 위해서는 cnt(l,r,d)는 최대로하고 cnt(l,r,c)는 최소로 만들어야 한다. 그래서 모든 인덱스를 순회하면서 l이 가장 작을 때를 저장해놓고, r이 가장 클 때를 저장해놓아서 최종적으로 빼주는 방식이다.

그리디 풀이는 간단하다. 문제상황을 정리해보면 내가 찾아야 할 것은 c로 바꿀 어떤 수 d를 찾는 것이다. 1~n까지 배열을 돌면서 현재 나온 수 arr[i]의 빈도수를 매번 갱신한다. 그리고 만약 현재의 arr[i]가 d라면 즉, arr[i]에 연산을 수행해서 c로 바꾼다면 최종정답은 얼마가 되는지 매번 계산하는 것이다. cnt[i]배열은 현재까지 i라는 수가 몇번 등장했는지 저장하고 pref[i],suff[i]배열은 각각 c값이 등장한 빈도수를 저장하는 접두사와 접미사 부분합 배열이다. 먼저 cnt[i]값을 pref[]값과 비교한다. 이 말은 arr[i]값을 c로 변환하는게 이득인지 그냥 c값을 그대로 사용하는게 이득인지를 계산하는 부분이다. 그리고 이 결과값에 suff[]를 더해준다. 이 결과를 ans값과 비교해서 최대가 되도록 갱신해준다.

주의할 점 : .

-

배울 점 : 

dp풀이에서 구간의 (최대-최소)를 구하는 부분이 낯설었다. (밑의 코드의 56~60줄)

코드 : 

dp 풀이

#include <bits/stdc++.h>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline void showAll(T arr[],int st,int end,string sep=""){
    for(int i=st ; i<=end ; i++) cout<<arr[i]<<sep; }
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 500009;
 
int arr[SIZE];
int pref[SIZE],suff[SIZE];
vector<int> pos[SIZE];
 
int main(){
    int n,c;    scanf("%d %d",&n,&c);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        
        if(arr[i]!=c)
            pos[arr[i]].push_back(i);
    }
 
    for(int i=1 ; i<=n ; i++){
        pref[i]=pref[i-1]+(arr[i]==c);
    }
    
    int ans=0;
 
    for(int i=1 ; i<=500000 ; i++){
        vector<int> v;
        for(int j=0 ; j<pos[i].size() ; j++){
            v.push_back(pref[pos[i][j]]);
        }
 
        int mn=1<<30;
        for(int j=0 ; j<v.size() ; j++){
            mn=min(mn,j-v[j]);
            ans=max(ans,j+1-v[j]-mn);
        }
    }
 
    printf("%d\n",ans+pref[n]);
 
    return 0;
}
/*

*/

그리디 풀이

#include <bits/stdc++.h>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline void showAll(T arr[],int st,int end,string sep=""){
    for(int i=st ; i<=end ; i++) cout<<arr[i]<<sep; }
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 500009;
 
int arr[SIZE];
int pref[SIZE],suff[SIZE],cnt[SIZE];
 
int main(){
    int n,c;    scanf("%d %d",&n,&c);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
 
    for(int i=1 ; i<=n ; i++){
        pref[i]=pref[i-1]+(arr[i]==c);
    }
    for(int i=n ; i ; i--){
        suff[i]=suff[i+1]+(arr[i]==c);
    }
 
    int ans=0;
    for(int i=1 ; i<=n ; i++){
        cnt[arr[i]]++;
        cnt[arr[i]]=max(cnt[arr[i]],pref[i-1]+1);
        ans=max(ans,cnt[arr[i]]+suff[i+1]);
    }
    printf("%d\n",ans);
 
    return 0;
}
/*

*/