[BOJ] 13900번: 순서쌍의 곱의 합

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

아... 그냥 재귀 함수로 돌아도 될 텐데 문제 풀 때 이상하게 규칙 찾느라 이렇게 풀었다.

2, 3, 4면 

2 * 3 + 3 * 4 + 2 * 4 -> 2(3 + 4) + 3 * 4 이렇게 묶어서 생각했더니 아래 코드가 나왔다. 16ms를 받았는데 더 짧고 빠르게 할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int number[100001];
long long sum = 0;
long long sx = 0;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &number[i]);
    sort(number, number + n);
    for (int i = 0; i < n; ++i)
        sum += number[i];

    for (int i = 0; i < n - 1; ++i)
    {
        sum -= number[i];
        sx += (number[i] * sum);
    }

    printf("%lld\n", sx);

    return 0;
}

이렇게도 풀 수 있습니다.

#include <iostream>

using namespace std;
typedef long long ll;
ll N, data, sum, ans;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> data;
        ans += sum * data;
        sum += data;
    }
    cout << ans;
    return 0;
}