백준 13900번. 순서쌍의 곱의 합 (파이썬)

문제

 

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

13900번: 순서쌍의 곱의 합

 

 

 

문제 풀이

 

이 문제를 푸는 데 수많은 시행착오를 거쳤다...

일단 결론부터 말하자면, 순서쌍 하나하나 더하는 것이 아닌 결합법칙을 사용해서 여러개의 순서쌍을 한 번에 더하는 것이 주요 포인트!!

 

반복문 사용을 최소한으로 해서 시간복잡도를 줄이고, 연산을 적게 사용해서 같은 시간복잡도더라도 더 빠르게 결과를 얻을 수 있도록 만들어야한다.

 

 

 

 

입력값이 1 2 3 4가 주어진 상황이라고 해본다. 결합법칙을 사용하면,

 

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

              (2 * 3) + (2 * 4) = 2 * (3 + 4)

                            (3 * 4) = 3 * (4)

 

위와 같이 표현해 연산 횟수를 줄일 수 있다.

 

import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split())) #ex) 1 2 3 4

sum=sum(arr)    #ex) sum = 1 + 2 + 3 + 4 
res=0

for x in arr:   #ex) x = 1
    sum-=x      #ex) sum = 2 + 3 + 4
    res+=sum*x  #ex) res = 1 * (2 + 3 + 4) 

print(res)

 

 

 

삽질한 과정

 

1.

이중 for문으로 시간초과

 

import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
sum=0
for i in range(0,n-1):
    for j in range(i+1,n):
        sum+=arr[i]*arr[j]
print(sum)

 

2.

4 * 3, 4 * 2, 4 * 1, ... 과 같이 역순으로 덧셈을 진행했다. 스택의 pop() 기능을 활용함으로써 시간복잡도를 O(N) 으로 줄일 수 있었으나, 연산 횟수가 많아 시간초과

 

import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))

l=len(arr)
last=l-1
j=last-1
sum=0

while l!=1:
    sum+=arr[last]*arr[j]
    if j==0:
        arr.pop()
        l-=1
        last-=1
        j=last-1
    else:
        j-=1
print(sum)

 

 

 

배운 점

 

1. 수학 관련 문제 상황이 주어진다면, 문제 상황 그 자체를 구현하는 것도 좋지만 수학법칙 및 규칙을 이용해서 알고리즘을 간단하게 만들어보자.