이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 C++ 프로그램을 작성하여 인접한 요소들 간 차이의 최대 합(maximum sum of difference of adjacent elements)을 구하는 것입니다.
문제 설명
크기가 N인 배열의 모든 순열(permutation)에 대해 인접한 두 요소 간 절댓값 차이의 합을 계산하고, 그중 가장 큰 값을 찾습니다.
예제를 통해 문제를 이해해 보겠습니다.
입력
N = 4
출력
7
설명
크기 4의 모든 순열과 각각의 인접 요소 차이 합 :
{1, 2, 3, 4} = 1 + 1 + 1 = 3
{1, 2, 4, 3} = 1 + 2 + 1 = 4
{1, 3, 2, 4} = 2 + 1 + 2 = 5
{1, 3, 4, 2} = 2 + 1 + 2 = 5
{1, 4, 2, 3} = 3 + 2 + 1 = 6
{1, 4, 3, 2} = 3 + 1 + 1 = 5
{2, 1, 3, 4} = 1 + 2 + 1 = 4
{2, 1, 4, 3} = 1 + 3 + 1 = 5
{2, 3, 1, 4} = 1 + 2 + 3 = 6
{2, 3, 4, 1} = 1 + 1 + 3 = 5
{2, 4, 1, 3} = 2 + 3 + 2 = 7
{2, 4, 3, 1} = 2 + 1 + 2 = 5
{3, 1, 2, 4} = 2 + 1 + 2 = 5
{3, 1, 4, 2} = 2 + 3 + 2 = 7
{3, 2, 1, 4} = 1 + 1 + 3 = 5
{3, 2, 4, 1} = 1 + 2 + 3 = 6
{3, 4, 1, 2} = 1 + 3 + 1 = 5
{3, 4, 2, 1} = 1 + 2 + 1 = 4
{4, 1, 2, 3} = 3 + 1 + 1 = 5
{4, 1, 3, 2} = 3 + 2 + 1 = 6
{4, 2, 1, 3} = 2 + 1 + 2 = 5
{4, 2, 3, 1} = 2 + 1 + 2 = 5
{4, 3, 1, 2} = 1 + 2 + 1 = 4
{4, 3, 2, 1} = 1 + 1 + 1 = 3위 결과에서 최댓값은 7이며, {2, 4, 1, 3} 또는 {3, 1, 4, 2} 순열에서 얻어집니다.
풀이 접근 방법
이러한 유형의 문제를 해결하려면 순열의 일반적인 합 패턴을 먼저 찾아야 합니다.
서로 다른 N 값에 대한 인접 요소 차이의 최대 합은 다음과 같습니다.
N = 2, maxSum = 1 N = 3, maxSum = 3 N = 4, maxSum = 7 N = 5, maxSum = 11 N = 6, maxSum = 17 N = 7, maxSum = 23 N = 8, maxSum = 31
이 값들은 N에 따른 등차수열의 합 S(N)과 미지의 함수 F(N)의 덧셈 형태로 표현할 수 있습니다.
maxSum = S(N) + F(N), 여기서 S(N) = n(n-1)/2 이고, F(N)은 N에 대한 미지 함수입니다.
S(N)과 maxSum(N)을 이용해 F(N)을 역으로 구해 보면,
F(2) = 0 F(3) = 0 F(4) = 1 F(5) = 1 F(6) = 2 F(7) = 2 F(8) = 3
여기서 다음 사실을 도출할 수 있습니다. F(N)은 Int(N/2 - 1)이며, N이 2씩 증가할 때마다 1씩 증가하고, N이 2와 3일 때는 0입니다.
따라서 maxSum의 공식은 다음과 같이 정리됩니다.
maxSum = N(N-1)/2 + N/2 - 1 maxSum = N(N-1)/2 + N/2 - 2/2 maxSum = ( N(N-1) + N - 2 )/2 maxSum = ( (N^2) - N + N - 2 )/2 maxSum = ((N^2) - 2 )/2
이 공식을 활용하면 어떤 N 값이 주어지더라도 반복문 없이 O(1) 시간에 maxSum을 즉시 계산할 수 있습니다.
예제 코드
아래 프로그램은 위 풀이의 동작 방식을 보여줍니다.
#include <iostream>
using namespace std;
int calcMaxSumofDiff(int N){
int maxSum = 0;
maxSum = ((N*N) - 2) /2 ;
return maxSum;
}
int main(){
int N = 13;
cout<<"The maximum sum of difference of adjacent elements is "<<calcMaxSumofDiff(N);
return 0;
}출력 결과
The maximum sum of difference of adjacent elements is 83