[백준 19576] 약수

문제

www.acmicpc.net/problem/19576

19576번: 약수

 

문제 풀이

1. 약수관계를 생각해보면 1은 모든 수와 약수관계를 이루므로 와우매직을 사용하는 경우엔 1로 바꿔주면 된다.

 

2. 와우매직을 최소한으로 사용하기 위해선 기존의 수들이 최대한 많은 약수관계를 이뤄야하고, 이는 수들을 정렬했을 때 각 인덱스를 시작으로 해당 인덱스의 수와 다른 수들과의 약수관계를 이루는 길이를 구하고 그 중 최댓값을 n에서 빼주면 와우매직을 사용하는 최소횟수이다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, dp[5001];
vector<int> a;

int go(int cur) {
	int &ret = dp[cur + 1]; // dp[cur + 1] = cur + 1에서 시작했을 때 약수관계를 이루는 최대 길이 
	if (ret != -1) return ret;
	ret = 1;
	for (int nxt = cur + 1; nxt < n; nxt++) {
		if (cur == -1 || !(a[nxt] % a[cur]))
			ret = max(ret, go(nxt) + 1);
	}
	return ret;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	memset(dp, -1, sizeof(dp));

	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	cout << n - (go(-1) - 1);
}