[C++] 백준 19576번: 약수 - DP, Math

https://www.acmicpc.net/problem/19576

19576번: 약수

 

임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데,

바꾸는 횟수가 최소가 되어야한다.

 

처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고,

해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다.

그런데 코드를 돌려보니,

5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고,

그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구했다.

 

쉽게 말해,

5는 5로 나누어떨어지므로 dp[5] = 2일 것이고, 마찬가지로 dp[7] = 7이될것이다.

그런데 처음 접근했던 방식으로는 dp[35] = 5이므로 바꿀 필요가 없는 수열로 인식되지만,

사실은 5, 혹은 7을 바꾸어주어야하는 수열이다.

 

그렇기에 dp배열에는 원소를 넣어주고, 새로운 배열을 만들어 해당 약수의 값 + 1 한 값과 비교해가며 최댓값을 구했다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[5001], ans[5001];
int main(){
    int n, cnt=0; cin >> n;
    for(int i=0; i<n; i++) cin >> dp[i];
    sort(dp, dp+n);
    fill(ans, ans+n, 1);
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(!(dp[i]%dp[j])) ans[i]=max(ans[i], ans[j]+1);
        }
    }
    for(int i=0; i<n; i++) cnt=max(cnt,ans[i]);
    cout << n-cnt;
}