백준 11659번 : 구간 합 구하기 4

 

 

문제 접근

---

1. 값을 입력받을 때 합 배열을 만들어 간단하게 부분 합을 구하자. 
   
     별 다른 특이 사항은 없다. 입력받을 때 각 인덱스까지의 합을 저장하는 배열을 만들고, 추후 끝에서 시작을 빼는 방식으로 사이의 부분 합을 구할 수 있다.

 

 

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

11659번: 구간 합 구하기 4

 

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, Input, i, j;

	cin >> N >> M;

	vector<int> SumUntil(N+1, 0);

	while (N)
	{
		cin >> Input;

		SumUntil[SumUntil.size() - N] = SumUntil[SumUntil.size() - N - 1] + Input;

		N--;
	}

	while (M)
	{
		cin >> i >> j;

		cout << SumUntil[j] - SumUntil[i-1] << '\n';

		M--;
	}

	return 0;
}

 

 

 

느낀 점

---

    처음에 별 생각 없이 풀었다가 TLE가 나왔다. 분명 시간 복잡도가 $O(n)$이라 입력 최대가 100,000인 이상 1초를 초과할 일이 없는데 TLE가 나와서 뭐가 문제인가 싶었다.

 

    침착하게 다시 확인해 보니 ios_base::sync_with_stdio(0)를 추가하지 않아서, stdio와 iostream의 동기화가 비활성화되지 않아 생긴 이슈였다.

 

    간단하게 해당 구문을 추가해줌으로써 해결했다.

 

 

1. 조건문 판별에 쓰는 변수의 변경은 웬만하면 따로 처리해 주자.
   
     이전부터 조건을 판별할 때에서 증감 연산자(++/--)로 값을 변경해줬는데, 지금 와서 생각해보니 이 때문에 조건문 내에서 값을 착각하기 쉬워 보였다.
   
     따라서, 이런 실수를 줄이기 위해 앞으로는 값의 변경은 따로 처리해 주도록 하자.