[ SWEA 1265 ] 달란트2 (C++)

SWExpertAcademy의 달란트2( 1265 / D5 ) 문제이다.

[ 문제풀이 ]

1) 문제를 처음 읽고 어떻게 접근해야 할지 고민을 많이 했었던 문제이다.

   주어진 달란트의 수를 P개의 묶음으로 나눴을 때, 그 갯수들의 곱의 최댓값을 구해야 하는 문제이다.

   본인이 생각한 건 '각 묶음에 들어가는 값들의 간격을 최소화 시키는 것' 이었다.

   왜냐하면, 10개를 3묶음으로 나눌 때, 1 1 8 보다는 3 3 4 가 더 큰 값이 되고, 문제에서 주어진 이 그림들을 보면서

   이런 생각을 했다.

   사실 어떻게 증명할꺼냐 라고 물어본다면 증명은 못하겠지만, 이 문제의 답은 각 묶음에 들어가는 값들의 차이를

   최소화 시키도록 묶음을 만들었을 때 최댓값이 나오게 된다.

   그래서 전체 달란트의 갯수를 묶음의 갯수로 나눴을 때 나오는 몫으로 먼저 묶음들을 채워넣어 주었다.

   예를 들면 10개의 달란트를 3묶음으로 나누는 경우에는, 3 3 3 으로 나눠보는 것이다. 이렇게 되면 1개의 달란트가

   남게 된다. 그럼 여기서 하나의 묶음에 저 1개를 추가시켜서 3 3 4 로 만들어 주는 것이다.

   그럼 11개를 3묶음으로 나눠보자. 11 / 3 = 3 이기 때문에 3 3 3 으로 먼저 나눈 후, 나머지 2개의 달란트를 채워넣어

   줘야 하는데.. 3 3 5로 만들어줄지, 3 4 4 로 만들어 줄지에 대해서 생각을 해보자.

   묶음간의 차이가 최소가 되려면 3 4 4 가 맞는 경우이고, 실제로 답도 3 3 4 로 나눴을 때가 정답이다.

   이런 생각만 가지고 문제를 구현했는데 pass를 받았다..

   코드적으로 어려운 부분은 없으니 소스코드를 참고하도록 하자.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
typedef long long ll;
using namespace std;
 
ll Answer;
int N, Set;
 
void Input()
{
    cin >> N >> Set;
}
 
void Solution()
{
    Answer = 1;
    int A = N / Set;
    int B = N % Set;
 
    Answer = pow(A, Set);
    for (int i = 0; i < B; i++)
    {
        Answer = Answer / A;
        Answer = Answer * (A + 1);
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        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;
}