Algorithm/누적합

[틀림] [알고리즘] 백준 2632 피자판매 // 누적합, 원형배열

https://www.acmicpc.net/problem/2632* 풀이1dp로 해보려다 실패 * 풀이2원형을 선형으로 만드는 힘 (뒤에 고대로 붙이면 됨)구간쿼리는 누적합 (누적합은 1-idx로 하는게 편한듯)경우의수는 등장 횟수를 저장하라 start 의 범위 문제start [1,2,3] / 간격2 의 예시에서 막라운드는 [3,1] 이다.막라운드 일때, start index는 4다.4 = n(3) + interval(2) -1 이다. #includeusing namespace std; int n,m,target,ret;int a[2004], b[2004], pa[2004],pb[2004];map ma, mb; // int main(){ ios_base::sync_with_stdio(0); cin..

[알고리즘] 백준 10986 나머지합 // 누적합, 나누기

https://www.acmicpc.net/problem/10986 * 아이디어 % 문제는 분배법칙으로 막 나눠라.%m으로 나눈 누적합을 구하라쌍을 찾아 C2 하면 답이다.원래 값이 0인것도 답이다. 같은 값을 선택한 예시 -> s[4] - s[2] == 원본배열에서 초록칸부분 1,2와 같음즉, 같은값 에서 2개를 선택하는 경우의수 == 정답의 경우의 수  * 전체코드c는 ret를  long long으로 해야함 (파이썬은 정수값 무제한임)#include using namespace std;int n, m;long long arr[1000000 + 4], sum[1000000 + 4];long long ret;int main() { ios_base::sync_with_stdio(0); cin.t..

[알고리즘] 백준 11660 구간합 구하기5 // 2차원 누적합

https://www.acmicpc.net/problem/11660 * 풀이data 정의를 잘해야함2차원 누적합 채우는 방법위 + 왼 - 좌측위(중복덧셈) + 원본3 + 3 - 1 + 3쿼리 구하기 x2,y2사각형 의 누적합에서 # sum(x2,y2)범위밖 위 사각형을빼고  # sum(x1-1,y2) 범위밖 좌측 사각형을 빼고  # sum(x2,y1-1) 중복제거된 교집한 부분 사각형을 더해주면 된다.  #  sum(x1-1,y1-1) 답 : sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1) #중복뺄셈보완 * 전체코드#include using namespace std;int n, m;int arr[1025][1025], sum[1025][1025]; ..