parametric-search 썸네일형 리스트형 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보다 크다면,.. 더보기 BOJ 25405 - 레벨 업 (P1, KOI 2022 중등부 4, 고등부 3) 당시 정올 때(중등부) 섭태1만 긁고 빠졌던 문제. 잠시 그때 얘기를 하자면 1번부터 4번까지 맞은 문제가 하나도 없었고 다 조금씩 긁기만 했었다. 3번 주차타워 O(N^2) dp까지 생각해서 코딩했는데 원 처리 제대로 안해서 틀린 후 멘탈이 나가서 91점으로 마무리. (왜 동상?) 그 후에 1번도 못 풀고 현타와서 ps를 잠깐 끊고 수학을 했던 기억이 있다. 다시 복귀한 후 KOI 2023 1차 전에 이 문제를 46점까지 긁었고, 오늘 100점에 성공했다. 그래서 서브태스크마다의 풀이를 작성해보려고 한다. Subtask 1. (Nn; v.resize(n); for(auto &i : v)cin>>i; cin>>m>>k; while(m--){ sort(all(v)); for(int i = 0 ; i < k.. 더보기 이전 1 다음
