AlgorithmBOJ

백준 차이를최대로 10819

,

1. 백준 차이를최대로 10819

2. 컴퓨팅 스킬

  • #include헤더에 있는 next_permutation()함수를 호출하여 순열과조합을 구현합니다.
  • next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환합니다.
  • prev_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환합니다.
  • #include헤더에 있는 abs절대값 함수를 사용합니다.(해당조건)

반드시 정렬이 수행되어야만 올바를 결과값을 얻을 수 있습니다.

3. 컴퓨팅 사고

  • |A[0] - A[1]| + |A[1] - A[2]| + … + |A[N-2] - A[N-1]|의 조건에 따라 반복문을 통하여 해당조건에 순열의 첫번째 경우, 두번째 경우, …마지막 경우에 따라 int sum의 값에 저장한 후 그 값을 max값과 비교한다. 최대값을 구해야하므로 이러한 일련의 과정이 필요합니다.
  • sum += abs(v[i] - v[i+1]); 의 식으로 현재 순열과조합의 경우에서 값들의 합을 구합니다. 이때 i값과 i+1값의 범위가 벗어나지 않는지 반드시 확인합니다. for문을 v.size()만큼 순회하면 오버플로우가 발생합니다.
  • max값과 sum의 값을 비교한 후 sum의 값이 max값보다 클 경우 max값을 해당 sum의 값으로 업데이트 시켜줍니다.(최대값)
  • next_permutation의 수행이 모두 끝나면 현재 max을 출력합니다. 현재 최대값이 저장되어 있습니다.

4. 풀이

4.1. next_permutation을 사용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//
//  05_백준_차이를최대로_10819.cpp
//  algorithm-level-up
//
//  Created by kgh on 30/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    int n=0;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    int max = 0;
    sort(v.begin(), v.end());
    do{
        int sum = 0;
        for(int i=0; i<v.size()-1; i++){
            sum += abs(v[i] - v[i+1]);
        }
        
        if(max < sum){
            max = sum;
        }
    }while(next_permutation(v.begin(), v.end()));
    
    cout << max << "\n";
    return 0;
}
Share