백준 19576(약수)

www.acmicpc.net/problem/19576

19576번: 약수

요즘 자면서 많이 생각한 문제이다. 

dp[]인걸 알아야 하는 문제인것같다. 

 

일단 정렬을 해서, 지금 최대 몇 개의 배수 약수 관계인지 찾으면 된다. 

 

찾으려면 일단 N^2의 시간이 걸린다. 왜냐하면 각기 다른 것들끼리 비교를 해야되기 때문에.

 

이걸 그러면 어떻게 비교해야할지 생각하면 어딘가에 저장해서 dp[]를 이용해서 밑에서 부터 위로 올리면 편할 것 같다는 생각이 든다. 

 

예시에서 

24 10 4 6 3 이렇게 있는데 이걸 오름차순 정렬하면

 

3 4 6 10 24

이렇게 되고, 여기서 3부터 시작한다. 

 

3은 그 전 어떤 것과 나누어떨어지면 그 나누어 떨어진값들 중 dp[]+1이 최대가 되는 값을 dp[0]의 값으로 한다.

 

4도 마찬가지

 

24로 해보자

 

24는 dp[6]+1, dp[4]+1, dp[3]+1 이렇게 후보군 세개가 존재하고 

미리 dp[3],dp[4],dp[6]을 구해놨기 떄문에 바로 처리가 가능하다. 

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 5005

int arr[MAX];
int dp[MAX];
int cnt, n;

void solve(int idx) {
	for (int i = idx; i >= 0; i--) {
		if (arr[idx] % arr[i] == 0) {
			dp[idx] = max(dp[i] + 1, dp[idx]);
		}
	} 
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	
	for (int i = 0; i < n; i++) {
		solve(i);
	}
	for (int i = 0; i < n; i++) {
		if (dp[i] > cnt)cnt = dp[i];
	}
	cout << n - cnt;
}