728x90 반응형 arithmetic-geometric mean1 [Python] 최고의 집합 최고의 집합문제 출처: 프로그래머스난이도: level 3참고: 없음input size: $1 \le n \le 10^4$, $1 \le s \le 10^8$(주관) 자료구조: 없음(주관) 알고리즘: 수학(주관) 예상 시간복잡도: $O(n)$합이 $s$인 $n$개의 자연수 집합을 구하고, 그 중 원소의 합이 최대인 집합을 오름차순으로 정렬한다. STEP 1. 관찰과 직관프로그래머스에 주어진 예시가 $n=2$라서 와닿지는 않는다.왜냐면 $n=2$인 경우에 너무 쉽게 찾을 수 있다.$a_1 = x, x_2 = s-x$라 하면 곱 $f(x) = x(s-x)$이고 이차함수의 최댓값은 $x=s/2$인 지점이다.물론 정수이므로 $a_1 = \lfloor s/2 \rfloor$, $a_2 = s-a_1$으로 간단히 찾.. 2024. 7. 2. 이전 1 다음 728x90 반응형
