기로에 서다

문제 www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 문제 풀이 1. 약수관계를 생각해보면 1은 모든 수와 약수관계를 이루므로 와우매직을 사용하는 경우엔 1로 바꿔주면 된다. 2. 와우매직을 최소한으로 사용하기 위해선 기존의 수들이 최대한 많은 약수관계를 이뤄야하고, 이는 수들을 정렬했을 때 각 인덱스를 시작으로 해당 인덱스의 수와 다른 수들과의 약수관계를 이루는 길이를 구하고 그 중 최댓값을 n에서 빼주면 와우매직을 사용하는 최소횟수이다. 코드 #include using namespace std; int n, dp[5001]; vector a; int go(int cur) { i..