백준 13900번 순서쌍의 곱의 합 [부분합] :: 마이구미

이번 글은 백준 알고리즘 문제 13900번 "순서쌍의 곱의 합" 을 다뤄본다.

최근에는 서강대학교 프로그래밍 대회에서 출제된 문제이다.

정답률이 30%이하로써, 단순히 쉬운 문제는 아닐 것이다.

풀이 방법은 많겠지만, 부분합으로 일반적으로 접근할 수 있다.

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

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

처음에는 동적계획법 느낌으로 접근하려했다.

2를 뽑을 경우 나머지 3, 4를 뽑을 수 있고, 3을 뽑을 경우 4를 뽑을 수 있다.

쉽게 2개의 반복문을 통해 구현할 수 있겠다고 생각했다.

// sum[i][j] = 하나는 i를 뽑는 기준으로, j를 뽑았을 때까지 합

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

하지만 런타임 에러가 발생했다.

테스트 케이스를 고려하지 않았다.

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

2차원 배열을 단순히 변수로 바꾸었다.

이 경우, 문제는 간신히 정답으로 이끌 수 있다.

하지만, 문제가 바라는 풀이는 아니다.

조금 더 속도 개선을 해보자.

이 문제의 규칙을 찾을 수 있었다.

입력이 1 2 3 4 주어졌을 경우를 보자.

// 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)

위와 같이 식을 바꾸어 규칙을 찾을 수 있다.

얻은 식을 통해서 부분합을 이용하여 접근할 수 있다.

for (int i = 1; i < n; i++) {
    sum[i] += sum[i - 1] + array[i];
}

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

또한, 이 문제의 주의할 점은 int형이 아닌 long형으로 접근해야한다.

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 13900번 "순서쌍의 곱의 합" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/math/13900.java