[백준] 순서쌍의 곱의 합 - 13900번 문제 (Python)

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

13900번: 순서쌍의 곱의 합

---

문제

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

예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다.

입력

첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000)

두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다.

출력

모든 경우의 곱의 합을 출력한다.

코드 정답

처음 틀린 코드

import sys
input = sys.stdin.readline

# 13900
n = int(input())
num = list(map(int, input().split()))
li = []

for i in range(n-1):
    for j in range(i+1, n):
        li.append(num[i] * num[j])

print(sum(li))

수정 코드

import sys
input = sys.stdin.readline

# 13900
n = int(input())
num = list(map(int, input().split()))
result = 0
acc = 0

for i in range(n):
    result += num[i] * acc
    acc += num[i]

print(result)

풀이

처음에는 단순히 시간 복잡도와 메모리 초과를 신경쓰지 않고 코드를 짜보았다.  첫 번째 행에서는 정수값을 입력받고 두 번째 행에서는 정수값을 여러개 입력받아 띄워쓰기를 기준으로 분류하여 리스트 형식으로 만들어냈다. 이후 반복문을 사용하여 계산된 값을 li 라는 변수에 순차적으로 인덱스에 값을 추가시킨 후 변수 li에 존재하는 값을 모두 더한 값을 출력하였다. 이렇게 할 시 값은 맞지만 당연히 메모리 초과와 시간 초과라는 오류가 발생하게 되었다.

 

그렇기 때문에 코드를 수정하여보았다. 똑같이 정수값을 입력받았지만 result 와 acc 라는 변수를 0이라는 초기값을 가지게 한 채로 만들었다. 이후 반복문을 사용하여 num 배열에 저장된 인덱스 값과 acc 값을 곱한 값을 result 라는 변수에 저장하였고 다음 행에는 num[i] 에 저장되어 있는 값을 acc 값과 더하여 acc에 저장하였다. 반복문이 끝나게 된다면 result 에 저장된 값을 출력해주었다. 이렇게 한다면 이중 for 문을 사용하지 않아 시간 복잡도가 감소되고 메모리 초과 부분을 잡아낼 수 있게 된다.