백준 24265번 풀이

문제

주어진 알고리즘의 수행 시간 출력하기

풀이

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

당최 무슨 언어인지 모르겠는 이 코드를 보자. 범위가 24264번 문제와 달리 고정이 안됐다…? 그치만 반복문은 두 개라는 그 사실은 변함이 없으므로 다차(2차)라는 것 역시 변하지 않는다. 그럼 패턴만 파악하면 되겠네요? 예, 그렇죠.

일단 7을 넣었을때 왜 21이 나오는지 알아야 하니 파이썬으로 짜보자.

import sys

k = int(sys.stdin.readline())

sum = 0
for i in range(1, k):
    for j in range(i+1, k+1):
        print(i,j)
        sum += 1

print(sum)

저기에 7을 넣으면

1: 2, 3, 4, 5, 6, 7
2: 3, 4, 5, 6, 7
3: 4, 5, 6, 7
4: 5, 6, 7
5: 6, 7
6: 7

이렇게 나온다. 이제 위에서부터 콜론 옆 숫자가 몇 개인지를 보자. 6+5+4+3+2+1 하면 21이네? 그럼 5를 넣으면 10인가요? 네. 이거 초항이 1 마지막 항이 n-1이고 공차가 1인 등차수열의 합이다.

import sys

k = int(sys.stdin.readline())

a = list(range(1,k))
print(sum(a))
print(2)

난 걍 배열 만들어서 배열 합 출력했는데 등차수열 공식 이용하실 분들은 그거 쓰십셔.