[Codefocres 1061C] Multiplicity

[Codefocres 1061C] Multiplicity - 1700

문제 설명 : 

어떤 집합의 원소 N개가 주어진다. 그 집합에서 부분집합(subset)을 만들 건데 부분집합의 원소의 개수는 1개 이상이여야 하고 i번 째 원소는 반드시 i로 나누어 떨어져야 한다. 이 두 조건을 만족하는 부분집합을 만들 수 있는 경우의 수를 구하는 문제이다.

풀이 : 

메모리 초과, 시간 초과와 싸워야 하는 문제이다.

각 원소가 1~N 사이의 정수 j로 나누어 떨어지는지 확인한다. 나누어 떨어진다면 그 원소는 subset의 j번째 원소가 될 자격이 있는 것이다. 이를 만약 현재 보고 있는 원소가 j로 나누어 떨어진다면 그 경우의 수를 2차원 dp로 나타내면 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]이 된다. 여기서 i는 현재 길이가 i인 부분집합을 만들고 j번 째 원소를 보고있다는 의미이다. 만약 j로 나누어 떨어지지 않는다면 dp[i][j] = dp[i-1][j]이고 이전 경우의 수를 그대로 가져온다는 의미이다. 하지만 이 문제에서 N의 최대 크기는 10만이므로 메모리는 N*N으로 잡으면 메모리가 초과된다. 따라서 이 문제는 dp테이블을 1차원으로 잡을 수 밖에 없다. 1차원이 가능한 이유는 현재의 dp테이블을 채우는 데에는 오직 지난 1회의 데이터만 참조하기 때문이다. 하지만 여기에도 다른 문제가 있다. 현재 dp테이블 dp[i]를 채우기 위해서는 dp[i-1]은 이미 갱신되었기 때문에 지난 시행에서 저장되어 있었던 dp[i-1]은 이미 정보다 사라졌다. 이를 해결하기 위한 방법이 바로 값이 크기를 오름차순이 아닌 내림차순으로 정렬 해놓는 것이다. 내림차순(큰 수 -> 작은 수)으로 보면 dp테이블도 큰 수 -> 작은 수 방향으로 채워질 것이기에 이전 값이 사라질 걱정을 하지 않아도 된다. 

여기까지 하면 메모리 초과는 해결했다. 하지만 시간은 O(N^2)이라서 역시 시간이 터진다. 시간은 어떻게 줄여야 할까?

그 방법은 각 원소들의 약수들만 따로 구해서 그 값들일 때만 갱신하는 것이다. 약수가 아닐 때는 나누어 떨어지지 않을 것이므로 이전 값과 동일할 것이다. 따라서 굳이 갱신할 필요가 없다. 갱신은 오직 원소가 j로 나누어 떨어질 때만이므로 전처리로 모든 원소들의 약수들을 구해 놓은 뒤, 약수일 때만 갱신해주면 된다. 어떤 수의 약수의 최대 개수는 2*sqrt(n)개 정도로 계산하면 된다(sqrt(x)=x의 제곱근 연산). 따라서 1~N을 모두 봐야했던 기존의 시간복잡도 O(N)에서 O(sqrt(N))으로 줄어들었다. 이에 대한 구현은 아래 코드 54~58줄에 나와있듯이 에라토스테네스의 체를 살짝만 변형하면 된다.

주의할 점 : 

-

배울 점 : 

1차원 dp를 사용할 때 지난 값을 사용하기 위해서 역순으로 보는 방법을 사용할 수 있다.

일정 범위에 속하는 모든 수들이 각각 가지는 약수들을 에라토스테네스의 체를 응용해서 구현할 수 있다.(54~58줄)

같은 1700 난이도라도 dp 유형의 문제는 아직 어려운 것 같다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
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;
typedef pair<int,int> Cord;
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;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
 
inline void showAll(vector<int> &v,int NL_or_space=0){ 
    //0 is space(default), 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 100009;
const int MOD=1e9+7;
const int MAX_RANGE=1e6+9;
ll dp[MAX_RANGE];
vector<int> factor[MAX_RANGE];
 
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=1 ; i<MAX_RANGE ; i++){
        for(int j=i ; j<MAX_RANGE ; j+=i){
            factor[j].push_back(i);
        }
    }
 
    for(int i=1 ; i<MAX_RANGE ; i++)
        reverse(factor[i].begin(),factor[i].end());
 
    dp[0]=1;
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
 
        for(int here:factor[inp]){
            dp[here]=(dp[here]+dp[here-1])%MOD;
        }
    }
 
    ll ans=0;
    for(int i=1 ; i<=n ; i++) ans=(ans+dp[i])%MOD;
 
    printf("%lld\n",ans);
    return 0;
}