윤만석

문제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..

시간 제한메모리 제한제출정답맞힌 사람정답 비율 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이 ..

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..