Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
[LeetCode] 2862. Maximum Element-Sum of a Complete Subset of Indices (C++)
EVEerNew 2023. 9. 26. 17:22문제
https://leetcode.com/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
풀이
난이도: Hard
weekly contest의 최종 보스 문제.
https://leetcode.com/contest/weekly-contest-363/
Contest - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제를 파악하는 것도 어려웠는데 이리저리 인수분해 해서 만든 코드도 결국 특정 케이스에서 계속 실패해서 정답을 참고하였다.
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
집합의 구성은 모든 요소들이 서로 한쌍씩 곱할 때 제곱수이어야 한다.
제곱수(var*var)를 만드는 정수를 var라고 하자.
var를 1에서 n까지 순서대로 만들면, 제곱수는 1, 4, 9, 16, 25, ... 이런 식으로 이어진다.
이 제곱수들은 서로 한쌍씩 곱하더라도 (var1*var1) x (var2*var2) = (var1*var2) x (var1*var2) 이기 때문에 다시 제곱수가 된다.
여기서 base라는 변수를 1에서 n까지 늘려가며 제곱수들에 곱해보자.
base = 1 일때, 제곱수들은 1, 4, 9, 16, 25,...
base = 2 일때, 제곱수들은 2, 8, 18, 32, 50,...
base = 3 일때, 제곱수들은 3, 12, 27, 48, 75,...
즉, (base * var1*var1) x ( base * var2*var2) = ( base * var1*var2) x ( base * var1*var2) 이기 때문에 다시 제곱수가 된다.
모든 배열의 숫자들은 양수이기 때문에 더해줄수록 값이 커진다.
따라서 base를 늘려가면서 제곱수들의 집합을 만들고, 집합이 가리키는 배열의 모든 수를 더해줘야 정답이다.
코드
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 2871. Split Array Into Maximum Number of Subarrays (C++) (0) | 2023.10.10 |
|---|---|
| [LeetCode] 2856. Minimum Array Length After Pair Removals (C++) (0) | 2023.09.30 |
| [LeetCode] 2861. Maximum Number of Alloys(C++) (0) | 2023.09.24 |
| [LeetCode] 295. Find Median from Data Stream (C++) (0) | 2023.07.22 |
| [LeetCode] 347. Top K Frequent Elements (C++) (0) | 2023.07.17 |