[백준] 13900번 - 순서쌍의 곱의 합 (부분합)

이 문제를 보고, 무작정 Brute Force로 풀면 되지 않을까라고 생각했다.

하지만 시간 제한 부분에서 (추가 시간 없음)을 보고, 이렇게 쉽게 나올리 없다고 생각하며 다른 방법을 생각해보았다.

 

예전에 비스무리한 문제를 풀었던 기억이 있는데, 잘 기억이 나지 않았다.

 

이렇게 잘 기억이 나지 않을 때는 식을 써보면 기억이 나기도 하여, 노트를 이용해 식을 작성해보았다.

 

예제 입력 2으로 먼저 식을 나열하면, 

 

(1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4)

 

위와 같이 나오는데, 정리를 해보면 아래와 같이 나온다.

 

(1*(2+3+4)) + (2*(3+4)) + (3*4)

 

아니다 다를까, 이렇게 바꿔보니 이 문제는 부분합으로 쉽게 풀리는 걸 알게 되었다.

 

✏️ 부분합이란?

부분합이란 배열이 존재하면, 미리 범위에 맞게 합이 계산된 배열을 만들어주는 방법을 말한다.

ex) psum

arr[1]

arr[1]+arr[2]

arr[1]+arr[2]+arr[3]

arr[1]+arr[2]+arr[3]+arr[4]

 

따라서 psum[] 배열을 만들어 합을 쉽게 구해주면, 이 문제는 쉽게 풀릴 것이다.

 

arr

1

2

3

4

psum

1

3

6

10

 

✏️ 구현 코드

 

#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
	long arr[100000];
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}
	long answer = 0;
	long psum[100000];

	psum[0] = arr[0];

	for (int i = 1; i < N; ++i) {
		psum[i] = psum[i - 1] + arr[i];
	}

	for (int i = 0; i < N - 1; ++i) {
		answer += arr[i] * (psum[N - 1] - psum[i]);
	}

	cout << answer;

}

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!