누적합1 [백준/11659/C] 구간 합 구하기 4 첫번째 시도 : 아무 생각없이 코딩했는데 정신차려보니 O(MN).. 당연히 시간초과(실버이상 문제는 날먹이 적은것같다 흑흑)#include int main(){ int N,M; scanf("%d %d",&N,&M); int arr[N]; for(int i=0; i 결론 : 검색해보니 누적합이라는 개념이 있는것같다. 그때그때 구간합을 계산하지 않고 미리 arr[1]부터 arr[k]까지의 수를 모두 더해놓고 구간합을 구할때는 누적합을 빼서 출력하면 시간복잡도가 대폭 줄어든다 (O(N))단순한 발상같은데 막상 생각해보려하면 안나온다..#include int main(){ int N,M; scanf("%d %d",&N,&M); int arr[N]; int rui[N]; sc.. 2025. 5. 26. 이전 1 다음 반응형