글 읽기 - 정렬이 왜 필요한지 궁금합니다

bitstr58 3년 전 0

안녕하세요. do-while 로 next_permutation () 써서 푸는데 틀렸습니다. 다른분들은 순열 함수 전에 sort를 하셨더라구요. 수열의 순서를 바꾸는건 마찬가지일텐데. 왜 sort() 를 해야 정답이 나오는지 궁금합니다. 도와주세요.

#include <iostream>
#include <cstdlib> 
#include <algorithm>  
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;	
}

pichulia 3년 전 1

next_permutation 함수가 어떻게 동작하는지 확인해보세요.

rasauq1122 3년 전 1

5 -1 -1 -1 -1 -1 가 입력으로 들어온다고 생각해봅시다.

이때의 '차이가 최대가 되는' 순열은 -1 -1 -1 -1 5 -1 일 것입니다.

다만, 5 -1 -1 -1 -1 -1은 이미 마지막 순열이므로 (내림차순이니까)

next_permutation을 사용하고자 하면, false를 return하고 올바르지 않은 값을 출력할 것입니다.

따라서, 수열을 정렬하여 next_permutation 함수를 통해 가능한 모든 순열에 대해 완전히 탐색할 필요가 있는 것입니다.

bitstr58 3년 전 0

@rasauq1122 @pichulia 님 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정렬이 왜 필요한지 궁금합니다

bitstr58 3년 전 0

pichulia 3년 전 1

rasauq1122 3년 전 1

bitstr58 3년 전 0

@rasauq1122 @pichulia 님 감사합니다!!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말