[ SWEA 1208 ] Flatten (C++)

SW Expert Academy의 Flatten(1208) 문제이다.

[ 문제풀이 ]

1) 이 문제는, 주어진 횟수만큼, 최대높이에 있는 상자를 최소높이에 있는 상자로 K번 옮겼을 때, 상자의 최고높이와 최저높이의

   차이를 구하는 문제이다.

   본인은, 상자들의 높이를 배열에 저장한 후, 정렬을 시켜주었다.(오름차순 정렬)

   한 번 덤프 시킬 때 마다, 배열의 가장 마지막 값을 -- 시켜주고, 가장 첫번째 값을 ++ 시켜준 후, 상자의 상태를 재정비 해 주었다

   위의 말을 구체적으로 알아보자 !

   예를 들어서 상자의 높이를 저장해둔 배열을 정렬 시켰을 때 배열의 상태가

   { 1, 1, 2, 3, 4, 5, 6, 6, } 이라고 생각해보자.

   이 상태에서 한번 덤프시킨 것과 같이, 최대높이에 있는 상자를 최소높이에 있는 상자로 옮기게 되면, 최대높이에 있는

   상자의 높이는 1만큼 감소할 것이고, 최소높이에 있는 상자는 1만큼 증가할 것이다.

   즉, { 2, 1, 2, 3, 4, 5, 6, 5 } 가 될 것이다.

   이 후, 또 한번 덤프시킨다 치고 배열의 가장 마지막값을 -- 시켜버리면, 최댓값이 아닌 값이 덤프되어버리는 현상이 발생한다.

   반대 상황도 마찬가지이다. 최소 값이 아닌 값이 덤프되어버리는 현상이 발생하게 된다.

   따라서, 배열을 재정렬 해 주었다. 정렬을 처음부터 끝까지 다시 시키는 방법도 있지만, 쓸데없이 메모리와 시간을 많이 낭비할

   것 같아서, 최소값이 앞으로 오도록, 최댓값이 가장 뒤로 오도록 구현해주었다.

   이 부분은 크게 어렵지 않으니 소스코드를 참고하도록 하자. (본문함수 : REMAKE() )

 

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int Height[MAX];
int N, Answer;
 
void Initialize()
{
    memset(Height, 0, sizeof(Height));
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < MAX; i++)
    {
        cin >> Height[i];
    }
    sort(Height, Height + MAX);        // 오름차순 정렬
}
 
void REMAKE()
{
    int Max_Value = Height[MAX - 1];
    int i = MAX - 2;
    while (1)
    {
        if (Height[i] <= Max_Value)
        {
            swap(Height[i + 1], Height[MAX - 1]);
            break;
        }
        i--;
    }
 
    int Min_Value = Height[0];
    i = 1;
    while (1)
    {
        if (Height[i] >= Min_Value)
        {
            swap(Height[i - 1], Height[0]);
            break;
        }
        i++;
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        Height[MAX - 1]--;
        Height[0]++;
 
        REMAKE();
    }
    Answer = Height[MAX - 1] - Height[0];
}
 
void Solve()
{
    int Tc = 10;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
 
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}