728x90
반응형
SMALL
백준 문제 풀이: 2399 [거리의 합]
문제 링크: https://www.acmicpc.net/problem/2399
문제 설명:
주어진 n
개의 정수에서 서로 다른 두 원소를 선택했을 때, 해당 두 수의 거리(절댓값 차이)의 합을 구하는 문제입니다.
거리는 모든 가능한 쌍 (i, j)
(i < j)에 대해 계산됩니다.
문제 해결 코드
#include <iostream>
using namespace std;
int arr[10001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
long long int ans = 0;
// 두 수의 거리 계산 (모든 가능한 쌍)
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
ans += 2 * abs(arr[i] - arr[j]); // 두 번 더해야 함
}
}
cout << ans << '\n';
}
예제 입력:
3
1 2 3
예제 출력:
8
코드 설명
- 핵심 알고리즘: 모든 가능한 쌍을 선택하여 거리(절댓값 차이)를 구한 후, 결과를 2배로 합니다.
- 구현 세부사항:
- 2중 반복문을 사용하여 모든 조합을 검사합니다.
- 거리는
abs(arr[i] - arr[j])
를 사용하여 구합니다. - 각 거리는 양쪽 방향(i → j, j → i)으로 존재하므로 2배 해줍니다.
- 시간 복잡도: O(N²), 모든 쌍을 탐색하기 때문에 최대 10,000² 연산 발생 가능
결과
모든 가능한 두 수의 거리 합을 정확히 계산합니다. 브루트포스를 활용한 조합 탐색을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!
728x90
반응형
LIST
'BAEKJOON > 수학' 카테고리의 다른 글
백준 11134번 [쿠키애호가](C++) -yes6686- 티스토리 (0) | 2025.03.26 |
---|---|
백준 11312번 [삼각 무늬-2](C++) -yes6686- 티스토리 (0) | 2025.02.16 |
백준 21921번 [블로그](C++) -yes6686- 티스토리 (0) | 2025.02.07 |
백준 6588번 [골드바흐의 추측](C++) -yes6686- 티스토리 (0) | 2025.02.07 |
백준 16884번 [나이트 게임](C++) -yes6686- 티스토리 (1) | 2025.01.27 |