반응형
https://www.acmicpc.net/problem/2559
💡 수열
- 이 문제는 무지성으로 풀이하면 [시간초과]가 당연히 발생하는 문제이다.
- 입력 크기가 최대 10^6이므로 O(n^2)으로 풀 시 시간초과가 발생한다.
- 결론적으로 이 문제는 "누적합"="부분합"을 이용하여 풀이할 수 있다.
- 누적합을 저장할 크기가 N+1인 벡터를 생성하고, 0으로 초기화한다.
- N+1개를 생성한이유는 0번 인덱스를 0으로써 활용하기 위함이다.
- 누적합 배열을 v라고 할 때, 만약 K=2이면 v[2]-v[0]은 두번째 값까지 더한 값에서 0번째 값까지 더한 값을 빼준 것이고, 이 값은 첫번째값과 두번째값을 더한 것이므로, 단순히 빼기를 통해 구간의 합을 구할 수 있고, 이로써 중복적인 더하기 연산을 피할 수 있으므로 시간을 단축할 수 있다.
- 예시
- 주어진 예시에서 5개만을 가져와 보았다.
- 주어진 5개의 숫자값들이 위의 배열과 같을 때, 아래 v배열은 각 값들의 누적합을 차례로 1번 인덱스부터 채워넣는다.
- 하나씩 살펴보면, v[1]에는 첫번째 값인 3을, v[2]에는 두번째값까지 더한 값(3+(-2))인 1을, v[3]에는 세번째값까지 더한...
- 이제 K가 2이므로, 연속한 두 값씩 더한 값을 구해보자. 이는 이미 구해둔 v[K]-v[0] 연산만을 통해 구할 수 있다.
- 첫번째 연속합을 max로 지정해주고, for문을 통해 K+1부터 N까지 진행하면 된다.
- 이 방법은, cin으로 숫자값들을 받을 때, 동시에 배열에도 누적합을 더해 놨기 때문에, 이 값을 이용해 차 연산만 해주고, 그 연산 결과가 가장 큰 값을 반환하면 되므로, 시간효율이 아주 좋다!
- 아래는 전체 코드이다.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N,K;
cin>>N>>K;
vector<int> v(N+1,0);
for(int i=1; i<N+1; i++){
int temp;
cin>>temp;
v[i]=v[i-1]+temp;
}
int max=v[K];
for(int i=K+1; i<N+1; i++){
max=(max<v[i]-v[i-K])?v[i]-v[i-K]:max;
}
cout<<max;
return 0;
}
이전에 유사한 누적합 문제를 풀어봐서 문제를 보자마자 바로 "누적합!!!"하며 풀 수 있었다.
코딩테스트를 준비하면서 여러 문제를 풀다보니, 점점 문제의 유형이 눈에 보이기 시작한 것 같다.
그래도 아직 갈길이 멀다...!!!
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 1051번 C++ "숫자 정사각형" 풀이 / 구현 문제 (0) | 2023.11.19 |
---|---|
[백준] 1032번 C++ "명령 프롬프트" 풀이 / 구현 문제 (0) | 2023.11.19 |
[백준] C++ 1158번 "요세푸스 문제" 풀이 / 자료구조 문제 (1) | 2023.11.18 |
[백준] 9935번 JAVA 골드4 "문자열 폭발" (0) | 2023.11.03 |
[백준] c++ 11047번 동전 0 문제풀이-그리디 알고리즘 풀이법 (2) | 2023.10.17 |