부분합 3

[백준] 1806. 부분합 (복습)

문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N (10 ≤ N 출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 골드4 부분합, 투포인터 문제입니다#include#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)#define mset(v) memset(v,0,sizeof(v));#define rep(i,a) for(int i=0;i pi;typedef tupleti;typedef vector vi;typedef vect..

baekjoon 2024.09.25

[백준] 11660. 구간 합 구하기 5

시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 28068 13432 10515 46.829% 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 ..

baekjoon 2022.09.08

[종만북] 부분 합

N명의 시험 성적이 내림차순으로 저장되어있는 배열 score이 있다고 할때 a등에서 b등까지 평균점수를 계산하자 평균점수를 계산할때는 score[a]에서 score[b]까지 더하고 b-a+1를 나누면 됩니다. 하지만 이 방법은 O(N)이 걸리게 됩니다. 따라서 부분합 배열 Sum을 사용하면 O(1)에 문제를 해결할 수 있습니다. 0 1 2 3 4 5 6 7 8 score 1 2 3 4 5 6 7 8 9 sum 1 3 6 10 15 21 28 36 45 부분합을 구현하는 함수는 다음과 같습니다 vector partialSum(vector score){ vectorret; int temp=0; for(int i=0;i0) ret-=psum[y1-1][x2]; if(x1>0) ret-=psum[y2][x1-1..

종만북 2022.09.08