백준 10819번 [차이를 최대로](C++) -yes6686- 티스토리

백준 문제 풀이: 10819 (차이를 최대로)

---

문제 링크: https://www.acmicpc.net/problem/10819

문제 설명:

주어진 수열을 순열로 재배치하여
다음 식의 최대값을 구하는 문제입니다: |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|.

---

문제 해결 코드

#include <iostream>
#include <cmath>
using namespace std;

int arr[9];     // 입력 배열
int carr[9];    // 순열을 저장할 배열
int visited[9]; // 방문 여부 확인

int n;          // 배열 크기
int maxAns = 0; // 최대값 저장

// 순열을 만들면서 최대값 계산
void sol(int d) {
    if (d == n) { // 모든 자리를 채운 경우
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sum += abs(carr[i - 1] - carr[i]); // 차이의 절댓값 누적
        }
        maxAns = max(maxAns, sum); // 최대값 갱신
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 방문하지 않은 원소 선택
            visited[i] = 1;
            carr[d] = arr[i]; // 순열의 현재 자리에 값 배치
            sol(d + 1);       // 다음 자리로 진행
            visited[i] = 0;   // 원상 복구
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n; // 수열의 크기 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 수열 입력
    }

    sol(0); // 순열 탐색 시작
    cout << maxAns; // 최대값 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 완전 탐색 (백트래킹): - 모든 가능한 순열을 생성하면서 조건에 맞는 값을 계산합니다.
• 절댓값 계산: - 순열이 완성되면 두 인접한 원소 간의 차이의 절댓값을 누적합니다.
• 최대값 갱신: - 모든 순열을 탐색하며 최대값을 갱신합니다.

세부 구현:

• visited: 중복되지 않도록 이미 사용한 원소를 체크합니다.
• carr: 현재 순열을 저장하는 배열입니다.
• sol(0): 순열 탐색을 0번째 인덱스부터 시작합니다.

시간 복잡도 분석

• 모든 순열을 탐색하므로 시간 복잡도는 **O(N!)**입니다.
• 각 순열에 대해 **O(N)**의 연산이 필요하므로 전체 복잡도는 **O(N! ⋅ N)**입니다.
• 입력 크기 N ≤ 8이므로 완전 탐색으로도 해결 가능합니다.

---

결과

주어진 수열에서 차이의 절댓값 합이 최대가 되는 경우의 값을 출력합니다.

• 입력 예시:

  6  
  20 1 15 8 4 10

• 출력 예시:

  62

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!