누적합3 [백준] 20648 - Rectangular Pasture (c++) https://www.acmicpc.net/problem/20648 문제 요약좌표평면에 있는 N마리의 소의 좌표가 주어진다. 직사각형 모양의 울타리로 소를 가둘 계획이다. 울타리 하나로 가둘 수 있는 소의 집합의 개수를 구해라. 풀이 (N^2)누적합스위핑좌표 압축N이 충분히 작기 때문에 N^2 풀이를 생각할 수 있다.두 소 i,j를 고정시키고 그 소를 포함하는 최소 넓이의 직사각형을 구한다. 그 직사각형을 위 아래로 확장시키는 경우의 수(직사각형 위에 점*직사각형 아래에 점)를 구한다. 각 x,y가 고유하기 때문에 이렇게 만든 직사각형에 포함되는 소의 집합 또한 고유하다. i#include using namespace std;#define ll long longvector xc,yc;ll sum[3000.. 2025. 1. 28. [백준] 9569 - No Change (c++) https://www.acmicpc.net/problem/9569 문제 요약사야 하는 물건 N개와 들고 있는 동전 K개의 가치가 주어진다. 꼭 순서대로 사야하며 여러개를 한 번에 살 수 있다. 또한 거스름돈을 받을 수 없다. 이 때 남기는 돈의 최대값을 구해라. 풀이 (2^KlogN)비트dp누적합이분탐색dp[k]; dp[i]=동전 비트마스크가 i일 때 살 수 있는 물건의 최대 개수로 정의 해준다. 물건 가격의 누적합 배열을 만들어 두면 이분탐색으로 logN에 업데이트를 해줄 수 있다. upper_bound(all(psum),psum[이미 먹은 개수]+쓸 동전 가치) 이렇게#include using namespace std;#define ll long longint main() { cin.tie(0.. 2025. 1. 20. [백준] 3233 - BRODOVI (c++) https://www.acmicpc.net/problem/3233Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 4번 문제 요약N크기의 강에 칸 마다 물고기에 개수가 주어진다. M개의 닻을 내릴 위치와 배의 크기가 주어질 때 배를 닻에서 벗어나지 않게 옮겨서 잡을 수 있는 물고기의 최댓값을 구해라. 풀이 (MlogM)스위핑DP누적합닻을 스위핑하면서 1차원 DP배열을 업데이트 해주면 된다. 배가 서로 겹칠 수 없기 때문에 현재 배가 전,후 닻까지 가지 못하게 하고 범위안에서 누적합으로 잡을 수 있는 물고기를 구해 업데이트 해준다. 배가 가지 못하는 곳도 생기기 때문에 갱신 했던 마지막 위치 부터 현.. 2024. 10. 31. 이전 1 다음