JArchive 프로그래밍 일기

문제

차이를 최대로 백준 10819번

리뷰

do while 문을 이용해서 next_permutation 함수가 false를 반환하기 전까지 계속 출력시킨다.

abs 함수를 검색해보면서 새로운 걸 배웠다.

#include <cstdlib>
int abs(int a)

#include <cmath>
double abs(double a)

int 형의 절대값 함수는 cstdlib 에 있고,

double, float 형의 절대값 함수는 cmath에 있다.

참고로 C언어 에서 int형 절대값 함수는 stdlib.h 에 속하고 double형 절대값 함수 abs는 math.h 에 있다.

#include <stdlib.h>
int abs(int a)

#include <math.h>
double fabs(double a)

next_permutation() 함수

혼자 푸는데 자꾸 틀려서 다른 분들 코드를 봤는데, 순열함수 전에 sort() 를 한 것이 내 코드와의 차이였다.

#include <algorithm>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

이 함수는 주어진 수열의 다음순열이 없으면 false 를 반환해준다.

'다음' 순열의 기준은 현재 순열보다 내림차순된 순열이 있느냐/없느냐다.

예를 들어, 1234 의 다음 순열은 1243

1234 -> 1243 -> 1324 -> 1342 ... -> 4321 이처럼 첫 수열은 오름차순이고 맨 마지막 수열은 내림차순임을 이용하여 구현된 함수다.

따라서 처음에 next_permutation 에 4321 을 넣고 실행하면, 이미 전부 내림차순이므로( == 다음순열이 없다고 판단) false 반환하고 종료한다.

cplusplus.com 의 next_permutation 예시는 아래와 같다.

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

// output 
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

코드

#include <iostream>
#include <cstdlib> // abs()
#include <algorithm> //  next_permutation( )
using namespace std;

// 차이를 최대로  

int N;
int a[10];

int main(void){

    int max_value = 0;

    cin >> N;

     for(int i = 0; i < N; i++){
         scanf("%d", &a[i]);
    }  // 입력받기 끝  

    sort(a, a+N); // 정렬 

     do{
         int max_tmp = 0;

         for(int i = 0; i < N-1; i++){
             max_tmp += abs(a[i]-a[i+1]);
        } 

        max_value = max(max_tmp, max_value);

    }while(next_permutation(a, a+N));

    cout << max_value;

    return 0;    
}