[백준] 13900 순서쌍의 곱의 합 with Python

📌 BOJ 13900 순서쌍의 곱의 합

💡 조건

1. N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱을 구하라.

2. (2 ≤ N ≤ 100,000)
N개의 정수는 (0 <= x <= 100000)

3. 수학 유형의 문제

🖥 소스 코드

from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
r, s = 0, sum(a)

for i in range(n):
    r += a[i] * (s - a[i])

print(r // 2)

🔖 예제 및 실행결과

예제

3
2 3 4

실행결과

26

⌨️ 문제 풀이

1. 숫자의 개수 N을 입력 받고, N개의 정수를 입력받아 list 에 저장한다.
   결과를 출력할 r 이라는 변수를 생성하고, N개의 정수를 입력받아 저장한 list를 sum() 함수를 사용해
   s에 저장한다.

2. 순서쌍의 곱은 아래와 같이 나타낼 수 있다. 만약 a, b, c, d의 숫자가 있다고 가정한다면
   a * b + a * c + a * d로 나타낼 수 있다. 쉽게 표현하자면, ab + ac + ad 로 표현할 수 있다.

3. 2번에서 표현한 식을 결합법칙을 통해 묶어주게 된다면 아래와 같이 변한다.
   a(b+c+d)

4. 여기서 (b+c+d) 는 s-a[i]라고 할 수 있다.
   그래서 결국 식은 a[i] * (s - a[i]) 과 같으며, r에 쭉 더해준다.

5. 여기서, ab는 ba와 같은데 표현은 저렇게 할 수 있다는 것을 기억해야한다.
   그러므로 r // 2를 통해 반으로 나누어 주면 답이 출력 될 수 있다.

💾 느낀점

1. 결합법칙이 중요합니다.