728x90
MinAbsSum c++
-
[codility] MinAbsSum c++Coding Test/codility 2022. 9. 23. 21:15
문제 문제 해결 각 원소로 만들 수 있는 합의 개수 구하고, 그 합들을 이용해 전체 합에서 가장 작은 수가 구해질 때 까지 빼나간다. 1. A행렬의 원소를 모두 양수로 전환한다. A원소에 1 or -1 곱한 뒤 합을 구하는 거라 A의 원소가 양수여도 상관없다. 2. 양수로 변환된 A행렬의 원소의 합을 구하고 최댓값도 구한다. 최댓값을 구하는 이유는 각 원소의 개수를 구하는 것이고, 전체 합을 구하는 이유는 답의 가장 최악의 경우는 전체 합이기 때문 3. 각 원소마다 돌면서 가능한 부분 합들을 구한다. 이전에 가능한 부분합이 있었다면, 단순히 현재 원소의 개수를 넣어준다. 처음 만들어진 부분합이라면, 재사용한 것을 표기하기 위해 -1 한다. 4. 부분 합들을 전체합의 절반까지 계산하면서 전체 합에서 2배만..