백준 13900 순서쌍의 곱의 합 문제 풀이
문제 파악하기
단순히 제시된 수열에서 두 수를 뽑아 곱하는 모든 경우를 구해 더하는 것을 문제 목표로 제시하고 있습니다. 가장 기초적인 코드로는 아래와 같이 제시할 수 있을 것입니다.
1
2
3
4
5
6
# n, nums = n, [...]
result = 0
for i in range(0, n):
for j in range(i, n):
if i == j: continue
result += nums[i] * nums[j]
주의 깊게 살펴봐야할 것은, 빡빡한 시간 제한에 비해 입력으로 주어지는 값의 크기가 꽤 크다는 사실입니다. 입력으로 주어질 수 있는 최대 크기인 10만개를 기준으로, 위에서 살펴본 코드는 (10만 * 10만 / 2)회의 처리를 수행해야할 것입니다.
문제 풀어보기
누적합
연산 규칙을 잘 찾아본다면, 연산식에서 일련의 규칙을 찾아낼 수 있습니다.
1
2
3
4
5
6
1 * 2 + 1 * 3 + 1 * 4
+ 2 * 3 + 2 * 4
+ 3 * 4
= 1 * (2 + 3 + 4)
+ 2 * (3 + 4)
+ 3 * (4)
위에서 확인 가능한 사실은 이전 처리에서 사용한 합계를 다음 처리에서 사용할 수 있다는 것입니다.
3 * 4부터 계산할 때, 다음 처리인 2 * (3 + 4) 에서 4는 재활용해 3을 더해서 사용할 수 있고, 그 다음 처리인 1 * (2 + 3 + 4)에서는 (3 + 4)를 재활용해 2를 더해서 사용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
part_sum = [0 for _i in range(n)]
part_sum[n - 1] = nums[n - 1]
for i in range(n - 2, 0, -1):
# 이전 처리 재활용
part_sum[i] = part_sum[i + 1] + nums[i]
# 혹은
part_sum = [0 for _i in range(n)]
part_sum[0] = nums[0]
for i in range(1, n):
# 이전 처리 재활용
part_sum[i] = part_sum[i - 1] + nums[i]
개념 코드로는 이렇게 생각할 수 있습니다. for문의 순회 방법은 덧셈 연산 순서 차이이므로 크게 신경쓰지 않아도 되고, 주의깊게 볼 점은 이전에 사용한 덧셈 연산 결과를 재사용한다는 것입니다.
실제로 계산식을 적용한다면 다음과 같이 작성하게 될 것입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Rust
fn compute(n: i64, nums: Vec<i64>) -> i64 {
let mut part_sum: Vec<i64> = vec![0; n as usize];
let mut result: i64 = 0;
part_sum[0] = nums[0];
for i in 1..n {
part_sum[i as usize] = part_sum[(i - 1) as usize] + nums[i as usize];
}
for i in 0..((n - 1) as usize) {
result += nums[i as usize] * (part_sum[(n - 1) as usize] - part_sum[i as usize]);
}
result
}
제출한 러스트 코드를 그대로 긁어와 읽기 어려울 수 있지만, 기본적인 매커니즘은 개념 코드와 크게 달라지지 않았습니다. 계속해서 부분적으로 합을 누적시켜 별도로 저장하고, 나중에 곱셈 처리 시 사용하면 됩니다.
이 처리의 핵심은 곱셈의 결합법칙으로, 실제로 입력 예시를 나열하고 손으로 수식을 작성하여 최적화 방법을 찾아야 했습니다.
답안 구현
여담
거의 완전히 동일한 문제로 두 문제가 더 있습니다.