[Baekjoon] 11659번: 구간 합 구하기 4

 

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

11659번: 구간 합 구하기 4

 

---

 

문제 해결 과정

착안

문제를 해결하기 위한 착안 과정에 실수가 많아서 이상한 생각의 흐름을 거쳐 답에 도달했는데 결국에는 올바른 방향으로 문제를 해결했지만 나중에 같은 실수를 반복하지 않기 위해 실수 과정을 기록해두려고 한다. 이상한 방법으로 문제를 풀기 전, 우선 문제를 해결하기 위해 올바르게 생각했던 부분은

 

• 크기 $N$의 배열에 각 인덱스 $i$마다 $1$부터 $i$번째 숫자를 더한 값을 저장한다.
• 위의 배열을 사용하여 문제를 해결한다.

 

이다. 이러한 배열을 이용해 어떻게 문제를 해결할 수 있을까 고민을 하면서 아래와 같이 이상한 생각들을 펼쳤다.

 

(이상하게 착안한 과정 1) 뜬금없이 문제랑 별 관련도 없는 수학자인 가우스(Johann Carl Friedrich Gauss)가 생각났는데, 이 사람이 어린 시절에 했던 일이 생각나서(위의 링크 참고) 나도 뭔가 숫자를 뒤에서부터 거꾸로 적어놓고 역방향으로 누적합을 구해보고 싶어졌던 것 같다(가우스가 했던 거랑은 완전 아무 상관 없다). 그래서 크기가 $N$인 배열을 하나 더 만들어서 정방향으로 누적합을 구한 결과(FwdTab)와, 역방향으로 누적합을 구한 결과(BwdTab)도 저장해놓고 이를 비교해보았다. 예제로 제공된 케이스에 대해서 살펴보면 아래와 같다.

 

$N$	1	2	3	4	5
$i$번째 숫자	5	4	3	2	1
정방향 누적합(FwdTab)	5	9	12	14	15
역방향 누적합(BwdTab)	15	10	6	3	1

 

이렇게 놓고 보니까, $i \sim j$번째 숫자까지의 누적합은 전체 누적합의 값에서 $1 \sim (i-1)$번째 숫자들의 누적합과 $(j+1) \sim N$번째 숫자들의 누적합을 뺀 것과 같다는 것을 알았다(여기까지도 내 생각에 뭐가 문제가 있는지 못 깨달음ㅋㅋ). 그래서 각각의 배열을 동적계획법(dynamic programming)을 이용해 값을 모두 구한 다음, FwdTab[$N - 1$]의 값($1 \sim N$번째 숫자의 합)으로부터

 

• $i > 1$인 경우, FwdTab[$i-2$]만큼 뺀다($1 \sim (i-1)$번째 숫자들의 누적합).
• $j < N$인 경우, BwdTab[$j$]만큼 뺀다($(j+1) \sim N$번째 숫자들의 누적합).

 

와 같은 과정을 통해 문제를 해결했다(메모리를 비효율적으로 사용할 뿐, 아예 틀린 접근은 아니므로 문제는 잘 해결된다).

 

(이상하게 착안한 과정 2) 위와 같이 문제를 해결하고나서 뭔가 이상한 것 같은 느낌이 자꾸 들어 아까의 정방향 누적합, 역방향 누적합 숫자들을 계속해서 보다가 한 가지 사실을 깨달았다(이때 당시만 해도 엄청나게 대단한 걸 깨달은 줄 알았음). 역방향 누적합의 배열인 BwdTab[$i$]의 값은 결국 $1 \sim N$번째 숫자들의 누적합에서 FwdTab[$i-1$]의 값을 뺀 값이라는 사실이었다.

 

$N$	1	2	3	4	5
정방향 누적합(FwdTab)	5	9	12	14	15
역방향 누적합(BwdTab)	15 = 15 - 0	10 = 15 - 5	6 = 15 - 9	3 = 15 - 12	1 = 15 - 14

 

와~ 그렇다면 굳이 역방향 누적합 배열을 선언하여 값을 저장하지 않아도 되니까 메모리를 획기적으로 줄일 수 있겠네 라고 생각해서 그거에 신나가지고 해당 부분을 수정했다. 또한, 역방향 누적합을 계산하려고 $N$개의 숫자를 입력받는 반복문과 누적합을 구하는 반복문을 별도로 돌리고 있었는데 이 부분도 간소화할 수 있었다.

 

(결국 제대로 착안한 과정) 그럼에도 불구하고 아직도 뭔가 놓치는 부분이 있는 것 같은 느낌이 들어 문제를 계속 살펴보다가 문득 내가 여태까지 불필요한 과정을 엄청 수행하고 있었다는 것을 깨달았다. $i$번째 숫자부터 $j$번째 숫자까지의 합을 구할 때 굳이 $1 \sim N$번째 숫자들의 누적합에서 다른 값을 뺄 필요 없이, 그냥 $1 \sim j$번째 숫자들의 누적합에서 $1 \sim (i-1)$번째 숫자들의 누적합을 빼면 된다는 것이었다. 대체 이걸 깨닫는데 왜 이렇게 오래 걸렸을까?

 

앞에서 거의 올바른 방향으로 생각을 다 해놓고 왜 이런 단순한 생각을 못했는지는 모르겠지만 이 사실을 알고 5 분간 기립박수를 치며 웃은 뒤, 제대로 프로그래밍해서 최종적으로는 효율적인 코드로 수정할 수 있었다.

 

구현

위에서 구체적인 내용을 다 언급하였기 때문에 추가적으로 설명할 것은 없을 것 같다...

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;

	vector<int> FwdTab(N);
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;

		FwdTab[i] = (i ? FwdTab[i - 1] : 0) + num;
	}
	
	while (M--)
	{
		int i, j;
		cin >> i >> j;

		cout << FwdTab[j - 1] - (i > 1 ? FwdTab[i - 2] : 0) << "\n";
	}
	
	return 0;
}

 

실행 결과

 

---

 

사실 문제를 해결하기 위한 착안을 제대로 못해서, 위에 기록한 내용보다 훨씬 더 심각한 뻘짓도 몇 번 했었다(당연하게도 메모리나 시간이 초과할 수 밖에 없는 코드들). 단순한 문제인데 괜히 너무 복잡하게 생각해서 오히려 헤맨 것 같다.