[BOJ/백준] 10819 차이를 최대로

● [문제번호 10819] 차이를 최대로

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

: 재귀

 

● 풀이 과정

: N과 M (5) 문제에서 (조건말고) 작업을 추가한 정도의 문제 같다.

 

: 특별한 것 없이 재귀를 이용한 DFS의 형태로 구현했다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

: N과 M (5)

https://pirateturtle.tistory.com/247

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// input : 입력할 배열
// num : input의 순열들을 저장할 배열
// visited : input의 원소가 num 배열에 있는 지 확인 (true : 있음 / false : 없음)
int input[8] = {0, };
int num[8] = {0, };
bool visited[8] = {false, };
int N, sol;

// |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 계산
int calculation()
{
    int total = 0;
    for(int i = 0; i < N - 1; i++)
        total += abs(num[i] - num[i + 1]);
    return total;
}

// 모든 순열에 대해 조사
void permutation(int cnt)
{
    // 순열이 만들어진 경우
    if(cnt == N)
    {
        // 반환값이 기존 최댓값보다 크면 저장
        int temp = calculation();
        
        if(sol < temp)
            sol = temp;
    }
    
    // input의 첫 원소부터 순서대로 저장
    for(int i = 0; i < N; i++)
    {
        // input 원소가 num 배열에 존재하지 않는 경우
        if(!visited[i])
        {
            // 1. num 배열에 있다고 표시
            // 2. num 배열에 input 원소 저장
            // 3. 재귀
            // 4. num 배열에 없다고 표시
            visited[i] = true;
            num[cnt] = input[i];
            permutation(cnt + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 배열 입력
    for(int n = 0; n < N; n++)
        cin >> input[n];
    
    // num 배열에 input 원소가 0개 이므로 0부터 시작
    permutation(0);
    
    // 식의 최댓값 출력
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 - 순열] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10972	다음 순열	https://pirateturtle.tistory.com/237
2	10973	이전 순열	https://pirateturtle.tistory.com/238
3	10974	모든 순열	https://pirateturtle.tistory.com/239
4	10819	차이를 최대로	https://pirateturtle.tistory.com/240
5	10971	외판원 순회 2	https://pirateturtle.tistory.com/241
6	6603	로또	https://pirateturtle.tistory.com/242