백준 1750 - 서로소의 개수

icpc.me/1750

 

수열이 주워지고 이들의 조합으로 만든 집합 중 원소들이 서로소가 됨을 만족하는 것 개수를 구하는 문제이다.

 

DP 테이블 구성이 어려울 수 있으나 집합의 개수와 유사한 형태로 짤 수 있다. 집합의 개수를 먼저 풀고 오는 게 이 문제를 보는데 도움이 될 수 있다.

 

테이블의 정의는 다음과 같이 된다.

 

DP[i][j] := i번째까지 원소 중에서 최대공약수가 j가 되게 하는 원소들로 이루어진 공집합이 아닌 집합의 개수

 

DP 테이블을 구성하더라도 어떻게 채우는지는 아직 감이 오지 않을 수 있다. 하지만 집합의 개수를 생각하여 다음과 같은 점화식을 생각할 수 있을 것이다.

 

k := gcd(j, k) = j라고 한다면

DP[i][j] += DP[i - 1][j] + DP[i - 1][k]

 

i - 1번째 수까지 써서 최대공약수가 j가 되는 경우를 그대로 가져오고 j와 k의 최대공약수가 j가 되도록 하는 k를 찾아 DP[i - 1][k]를 더해주는 방식이다.

 

하지만 이럴 경우, k에 대해 간결한 구현을 하기가 어려울 수 있다. k대신 다음과 같이 표현해보자.

 

seq[i] := 수열의 i번째 수라고 한다면

DP[i][j] += DP[i - 1][j]

DP[i][gcd(seq[i], j)] += DP[i - 1][j]

 

i번째 수에 대해 계산을 할 때 최대공약수를 이용함으로써 간결하게 구현할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
#define mod 10000003
 
using namespace std;
 
int seq[100];
int dp[100][100001];
 
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> seq[i];
        dp[i][seq[i]] = 1;
    }
 
    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j <= 100000; ++j)
        {
            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
 
            int cop = gcd(seq[i], j);
            dp[i][cop] += dp[i - 1][j];
            dp[i][cop] %= mod;
        }
    }
 
    cout << dp[n - 1][1];
}