[백준] 14929: 귀찮아 (SIB)

문제 링크

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

접근 방식 / 풀이

문제를 찬찬히 읽어보니 n개의 값이 주어지고, nC2로 가능한 모든 두 가지 값의 곱을 더한 것을 찾는 문제였다.

즉, 입력으로 $a, b, c, d$ 가 주어진다면, $ab + ac + ad + bc + bd + cd$ 가 정답이다.

해당 문제를 풀기 위해, 두 수의 곱을 이용해보기로 했다.
입력으로 주어진 모든 값을 더한 뒤, 제곱하게 되면

$(a, b, c, d) * (a, b, c, d) = a^2 + b^2 + c^2 + d^2 + 2ab + 2ac + 2ad + 2bc + 2bd + 2cd$

위와 같이 전개될 것이고, 이 과정에서 우리가 원하는 답의 형태, $2 * (ab + ac + ad + bc + bd + cd)$ 가 나온다.

그러므로 문제를 풀며 구해야 하는 것은
1. 모든 입력값의 합
2. 모든 입력값의 제곱의 합
이고, (1)의 제곱에 (2)를 뺀 뒤 2로 나누면 정답이 도출된다.

이렇게 방법을 알아냈기에 문제에서 생각해야 하는 점은 오버플로우 뿐이다.
개수는 10만 이하, 값은 절댓값 100 이하이기 때문에

값의 총 합은 -10,000,000 ~ 10,000,000 사이의 값
값의 제곱의 합은 0 ~ 1,000,000,000 사이의 값
이기 때문에 int형 내로 가능하지만,
값의 총 합의 제곱을 이용해야 하기에 값의 총 합을 저장하는 변수를 long long으로 선언했다.

---

답안 코드 링크 (Github)

Solution Github Link

정답 코드 (C++)

#include <iostream>

using namespace std;

void	fastio(void);

int main(void)
{
    int	num;
	int	tmp;
    int	square_num = 0;
    long long	add_num = 0;   

	fastio();
    cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> tmp;
		square_num += tmp * tmp;
		add_num += tmp;
	}
	add_num *= add_num;
	add_num -= square_num;
	cout << add_num/2 << "\n";
	return (0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}