[백준] 19576번 약수 (c++)

[문제]

19576번: 약수

---

[풀이]

#다이나믹_프로그래밍 #수학 #정수론 #정렬

이 문제는 알고리즘 분류가 전부 방법을 설명해준 문제였다. 정렬-DP 순서로 진행하면 풀린다.

 

1. 미네랄 수치를 배열에 저장한다.

2. 입력받은 수치를 오름차순 정렬한다.

3. 다이나믹 프로그래밍을 통해 경우에 따라 나누어 떨어지는(그냥 둬도 되는) 수치의 수를 센다.

4. 총 미네랄의 개수에서 dp[] 중 가장 큰 값을 빼준다.

---

 

(전체 코드)

#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
	int mineral, cnt = 0;
	long long min[5001];
	long long dp[5001] = { 0 };
 
	cin >> mineral;
 
	for (int i = 0; i < mineral; i++) {
		cin >> min[i];
	}
 
	sort(min, min + mineral);
 
	for (int i = 0; i < mineral; i++) {
		for (int j = i; j >= 0; j--) {
        	//나누어 떨어진다면 +1
		if (min[i] % min[j] == 0) dp[i] = max(dp[j] + 1, dp[i]);
		}
	}
 
	for (int i = 0; i < mineral; i++) {
		if (dp[i] > cnt)cnt = dp[i];
	}
	cout << mineral - cnt;
 
	return 0;
}