백준 13900 순서쌍의 곱의 합 문제 풀이
백준 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문의 순회 방법은 덧셈 연산 순서 차이이므로 크게 신경쓰지 않아도 된다.
주의깊게 볼 점은 이전에 사용한 덧셈 연산 결과를 재사용한다는 것이다. 계속해서 부분적으로 합을 누적시켜 별도로 저장하고, 나중에 곱셈 처리 시 사용한다.
마무리
이 처리의 핵심은 곱셈의 결합법칙으로, 실제로 입력 예시를 나열하고 손으로 수식을 작성하여 최적화 방법을 찾아야 했다.
거의 완전히 동일한 문제로 두 문제가 더 있다.