koi기출 썸네일형 리스트형 BOJ 2613 - 숫자구슬 (G2) 알고리즘 분류 Dynamic Programming Greedy Binary Search Parametric Search 풀이 풀이 1: Greedy, O(N^3) N이 최대 300이므로 O(N^3)까지 고려할 수 있다. 따라서 임의의 구간 [l, r]을 골라서, [l,r]의 합이 최댓값이 되게 할 수 있는지를 빠르게 구할 수 있으면 된다. [l,r]의 합을 x라 하자. 배열의 처음부터 시작해서 값을 연속해서 더해나간다. 이 때, 합이 x 초과일 경우 새로 그룹을 갱신한다. (단, 하나의 값이 x 초과일경우는 불가능하다.) [l,r]에 대해서는 예외처리를 해준다. 위 알고리즘은 x가 최댓값이 되게 하면서 그룹의 크기를 최소화하는 그리디적인 방법이다. 만약 위 알고리즘대로 만든 그룹의 개수가 m보다 크다면,.. 더보기 이전 1 다음
