다이나믹 프로그래밍 테크닉 - 어떤 것을 선택하거나 선택하지 않아서 부분집합을 만드는 방법의 수

1. 문제

 

1750번: 서로소의 개수 (acmicpc.net)

1750번: 서로소의 개수

 

2. 풀이

 

수열에서 어떤 원소는 선택하고 어떤 원소는 선택하지 않아 만든 부분집합의 원소들의 최대공약수가 1이 되는

 

부분집합의 개수를 구하는 문제

 

안풀어보면 대단히 어렵다.

 

dp[i][j]를 배열의 i번째 수까지 사용했을때, 최대공약수가 j가 되는 부분집합의 개수라고 정의

 

원소의 크기는 10만까지니까 최대공약수도 당연히 10만까지 가능할거고

 

여기서 중요한건 자기 자신만 사용하면 최대공약수는 자기 자신이다

 

초기화할때는 모든 i = 0,1,2,...,n-1에 대하여 dp[i][s[i]] = 1

 

이게 무슨말일까?

 

s = [2,4,3]인데 dp[2][s[2]] = dp[2][3] = 1이라는 뜻은?

 

(2,4,3)중에 2는 쓰지 않고 4도 쓰지 않고 3만 써서 (3)을 만들었다는 뜻이다.

 

비슷하게 dp[1][s[1]] = dp[1][4] = 1은?

 

(2,4)중에 2는 쓰지 않고 4만 써서 (4)를 만들었다는 뜻이다.

 

그렇다면 dp[2][gcd(4,3)]은?

 

(2,4,3)중에 2는 쓰지 않고 (4,3)만 썼다는 뜻이 된다.

 

그러므로, i = 0,1,2,..,n-1에 대하여 각각 하나씩만 쓴 상태에서 dp[i][s[i]] = 1로 초기화하고

 

i = 1,2,..,n-1에 대해 가능한 모든 최대공약수 j = 1,2,...,100000에 대하여...

 

dp[i][j]를 만들려면?

 

1) i-1번째 수까지 사용해서 이미 최대공약수가 j라면, i번째 수는 쓰지 않아도 되므로...

 

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

 

이건 인덱스 i에 왔을때, i번째 수를 쓰지 않는 방법의 수가 된다.

 

2) i-1번째 수까지 사용해서 최대공약수가 j일때, i번째 수를 사용해서 만든 최대공약수가 g = gcd(s[i],j)라면...

 

dp[i][g] += dp[i-1][j]

 

이건 인덱스 i에 왔을때, i번째 수를 선택해서 만드는 방법의 수가 된다.

 

이렇게 dp배열을 채우면 마지막에 dp[n-1][1]은 n-1번째 수까지 사용해서 최대공약수가 1이 되는 부분집합의 개수가 된다.

 

from sys import stdin

#수열에서 일부 원소를 선택해서 최대공약수가 1이 되는 방법의 수
def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

mod = 10000003

n = int(stdin.readline())

s = []

for _ in range(n):
    
    a = int(stdin.readline())
    s.append(a)

#dp[i][j] = i번째 수까지 사용해서 최대공약수가 j가 되는 경우의 수
dp = [[0]*(100001) for _ in range(n)]

for i in range(n):
    
    dp[i][s[i]] = 1 #자기 자신만 사용하면 최대공약수는 자기 자신이 된다

for i in range(1,n):
    
    for j in range(1,100001):
        
        #i번째 수를 사용하지 않아도, 최대공약수가 j가 되는 경우의 수
        dp[i][j] += dp[i-1][j] 
        dp[i][j] %= mod
        
        g = gcd(s[i],j)
        
        #i번째 수를 사용해서 최대공약수가 g가 되는 경우의 수는...
        #s[i]와 j의 최대공약수가 g가 되는 모든 j에 대하여,
        #i-1번째 수까지 사용해서 최대공약수가 j가 되는 경우의 수에 i번째 수만 추가하면 된다
        
        dp[i][g] += dp[i-1][j] 
        dp[i][g] %= mod

print(dp[n-1][1])

 

 

같은 수가 들어올 수 있다면...

 

처음에 초기화할때 dp[i][s[i]] += 1로 해야하는거 아니냐?

 

처음에 초기화할때는 해당 수 1개만 쓰는 방법의 수이고...

 

만약 s = [2,2,2,4]여서 dp[2][2]를 구한다고 한다면..?

 

처음에 초기화할때는 dp[2][2] = 1은 (2,2,2)에서 3번째 2만 쓴 (2)이고

 

나중에 2중 for문 돌때, dp[2][2] += dp[1][2]로 1번째 2만 쓴 (2)에서 2번째 2를 추가한 (2,2)가 더해진다.