배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수

 

주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다.

 

이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가?

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

어떤 수로 바꾸는가?에 대한 문제는 되지 않는다

 

1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다.

 

그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가?

 

주어진 배열을 먼저 정렬하고, 정렬된 배열에서 약수 관계가 되는 가장 긴 부분 수열을 구한다

 

예를 들어 [24,10,4,6,3]은 정렬하면 [3,4,6,10,24]이다.

 

여기서 서로 약수 관계가 되는 가장 긴 부분 수열은 [3,6,24]이다. 

 

이 부분은 바꾸지 말고 4,10만 1로 바꾸면 [3,1,6,1,24]이면 임의의 두 수가 서로 약수 관계가 된다

 

가장 긴 부분 수열은 가장 긴 증가하는 부분 수열 LIS를 구하듯이 구하면 된다

 

dp[i] = i번째 원소까지 봤을때 가장 긴 증가하는 부분 수열의 길이

 

배열을 정렬해두면 왼쪽에서 오른쪽으로 증가하는 상태이므로, i = 0,1,2,...,n-1에 대하여

 

j = 0,1,2,..,i-1을 순회하여 A[i]가 A[j]로 나누어 떨어지는지만 확인하면 충분하다

 

만약 A[i]가 A[j]로 나누어 떨어진다면 j번까지 길이에 i번 원소를 붙이면 되므로 dp[i] = dp[j] + 1

 

여기서 조심할 것은 dp를 [1]*n으로 초기화해야함

 

원소 하나는 그 자체로 길이가 1이니까

 

n = int(input())

A = list(map(int,input().split()))

A.sort()

INF = 10**18

dp = [1]*n

for i in range(1,n):
    
    for j in range(i):
        
        if A[i] % A[j] == 0:
            
            dp[i] = max(dp[i], dp[j] + 1)
            
print(n - max(dp))