[백준/C++] 11659번 - 구간 합 구하기 4

 

문제

https://www.acmicpc.net/problem/11659

 

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

 

 

입력

 

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

 

출력

 

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

풀이

 

구간합 구하기 문제인데 N개의 원소를 입력받고 M개의 구간의 합을 출력하는 문제였다.

 

M개의 구간마다 원소를 더해서 출력하기에는 시간이 오래 걸릴 것 같아서 숫자를 입력받을때 마다 숫자를 더해 리스트에 저장해 문제를 풀었다.

 

만약 구간이 i~j 라면 j번째 숫자까지의 합에서 i번째 이전 즉, i-1번째 구간까지의 합을 빼주면 된다.

 

처음에는 C++로 풀었는데 시간 초과가 떴다... 아무리 생각해도 시간초과가 걸릴 것 같지 않았는데 시간초과가 걸려서 '혹시 입력받는 구간의 수가 매우 적기 때문에 10만개의 숫자를 입력받고 계속 더하는 과정이 더 오래 걸리나?' 라고 생각했다.

 

하지만 막상 코드를 짜보니 그것도 아니였다. 결국 python으로 문제를 풀었는데 python은 같은 방법으로 문제를 풀었을 때 시간초과가 나지 않고 풀렸다...

 

다른사람들의 코드를 보니 python의 import sys처럼 C++자체에서 입력을 받을 때 시간을 줄이는 방법을 써서 시간 초과가 걸리지 않았다...

​

[참조]

 

​

jaimemin.tistory.com

 

 

 

!!!

ios_base::sync_with_stdio(false);

cin.tie(0);

​

속도를 빠르게 하기 위해서 위 코드를 넣어줬는데, 저 코드를 넣어주면 빨라지는 이유는 ios_base::sync_with_stdio; 라는 구문이 c의 stido와 cpp의 iostream을 동기화 시켜주는 역할을 하기 때문이라고 한다.

 

이 때 iostream과 stdio의 버퍼를 모두 사용해서 딜레이가 발생한다. 따라서 ios_base::sync_with_stdio(false); 를 작성해 동기화를 비활성화 시켜주어야 한다.

​

cin.tie(0) 는 cin과 cout의 묶음을 풀어준다고 한다.

 

기본적으로 cin과 cout이 묶여져있어서 출력과 입력이 코드가 짜여진대로 순서를 보장해준다고 한다. 만약 묶음을 풀면 작성된 코드가 cout이 먼저여도 입력을 먼저 받는 경우가 발생할 수도 있다고 한다.

​

마지막으로 endl; 보다 C스타일의 '\n'이 더 빠르다고 한다. 알고리즘의 실행 속도를 높이기 위해 \n을 애용하자...

 

 

Code

 

 

# include<iostream>
using namespace std;

//구간 합 구하기 4
int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N = 0, M = 0;
	cin >> N >> M;
	//int* lst = new int[N + 1]; //동적할당
	int lst[100001];
	lst[0] = 0;
	int c = 0;
	int a=0;
	for (int i = 1; i < N + 1; i++)
	{
		cin >> a;
		c += a;
		lst[i] = c;
	}
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << lst[b] - lst[a - 1] <<"\n";
	}
	return 0;
}

 

---

 

처음부터 속도를 빠르게 해주는 저런 코드가 있는걸 알았다면...

누가 C++ 친절하게 잘 알려주고 설명해주면 좋겠다 모르는게 너무 많아 ㅠㅠㅠㅠ

 

11659번: 구간 합 구하기 4