반응형 codeforce2 [CodeForce/C++] F. Multiplicative Arrays (Div.3) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 페르마의 소정리와 DP를 이용해서 풀 수 있는 문제다. 잘 생각해보면 이 문제는 k를 소인수 분해하는 것으로 시작할 수 있다는 것을 알 수 있다.왜냐하면 최대 길이 n의 배열의 곱이 k가 나오기 위해서는 배열 a의 안에 k의 약수들이 있다는 뜻이 되기 때문이다. 이를 이용하면 배열의 길이가 n일 때, 1을 제외한 k의 약수의 개수를 m이라고 하면 n-m개의 1과 m개의 k의 약수로 이루어진 배열의 조합을 구하는 문제로 볼 수 있다. 이를 이용해 DP로 문제를 해결할 수 있다. 아래와 같이 DP를 정의 하자. DP[k][i] = 1이 아닌 i개의 수를 곱해서 k를 만드는 경우의 수 그러면 .. 2025. 1. 23. [CodeForce] Codeforces Round 929 (Div. 3) [A ~ F] 풀이 HTML 삽입 미리보기할 수 없는 소스 Dashboard - Codeforces Round 929 (Div. 3) - Codeforces codeforces.com HTML 삽입 미리보기할 수 없는 소스 [#A] A번 문제는 단순한 문제다. 특정 수열이 주어지면 2가지 작업을 수행할 수 있다. 한 가지 작업은 위치를 재배열 하는 것이고, 나머지 작업은 특정 범위안의 수에 -1을 곱하는 것이다. 이때, 두 작업을 수행한 뒤 수열의 합의 최댓값을 구하면 되는 문제다. 수열의 합이 최댓값이 되기 위해서는 모든 수가 음수가 아닌 양수가 되면 된다. 그러므로 위치를 재배열 할 때 음수들이 전부 붙어있게 재배치하고, 그 범위에 -1을 곱하면 전부 양수가 되므로, 결과값은 모든 배열의 수의 절댓값을 더한 값과 같다... 2024. 2. 28. 이전 1 다음 반응형
