250x250
Notice
Recent Posts
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Flutter
- 객체관계형DB
- 계층형DB
- 메인 메모리 DB
- TOPCIT
- sync_with_stdio(0)
- compare구조체
- 네트워크형DB
- vector unique erase
- 정렬
- 객체 지향형 DB
- BOJ
- 백트래킹
- boj 11659
- c++
- 프로그래밍 언어
- 개발프레임워크의 기술 동향
- 소프트웨어 개발도구
- 개발프레임워크
- ANSI-SPARC
- 멀티미디어DB
- 프로그래밍 언어 기술 동향
- aws winscp
- 클라우드기반 IDE
- 공간DB
- Backtracking
- compare
- 시간초과
- 소프트웨어아키텍처 기술 동향
- 온라인처리
Archives
옐그's 코딩라이프
[boj][c++] 구간 합 구하기 4 (구간합/시간초과/11659) 본문
문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.
셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
제한
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N
풀이 방법
합을 구해야 함 -> 구간합 사용
최대 10만 번의 합 -> 맨 처음에 한 번만 싹 구해놓고 우려먹기!
시간 초과 조심 -> cin.tie(0)->sync_with_stdio(0); 을 사용해 입출력 속도 높이기
#include <bits/stdc++.h>
using namespace std;
int N, M;
int arr[100001];
int dp[100001]={0};
int main(){
cin.tie(0)->sync_with_stdio(0);
int x, y;
cin >> N >> M;
for(int i=0; i<N; i++) cin >> arr[i];
dp[0] = arr[0];
for(int i=1; i<N; i++){
dp[i] = dp[i-1] + arr[i];
}
for(int i=0; i<M; i++){
cin >> x >> y;
cout << dp[y - 1] - dp[x - 2] << '\n';
}
}
기억하고 넘어갈 점
1. 구해야 하는 것이 몇 번인지 횟수 확인하고 많을 경우, 최소화 방안 생각하기
- 맨 처음 한 번만 계산해서 싹 저장해놓기 등등
2. cin.tie(0)->sync_with_stdio(0); 항상 사용해서 입출력 속도 높이기
- C++에서 cin과 cout은 기본적으로 tie(연결)되어 있음
- cout으로 출력한 후에 cin으로 입력 받으면 그사이에 버퍼가 자동으로 비워짐
- 따라서 cin과 cout의 동기화를 끊어서 입출력의 효율을 높임
728x90
'c++ > boj' 카테고리의 다른 글
[boj][c++] 좋은수열 (백트래킹/시간초과/2661) (0) | 2024.01.19 |
---|---|
[boj][c++] 회의실 배정 (정렬/시간초과/1931) (0) | 2024.01.18 |
[boj][c++] N과 M (9) (15663) (1) | 2024.01.17 |
[boj][c++] N과 M (2) (15650) (1) | 2024.01.15 |
[boj][c++] 시간초과 해결방법(정렬 외/1920번) (0) | 2022.02.16 |