[ SWEA 7829 ] 보물왕 태혁 (C++)

SWExpertAcademy의 보물왕 태혁(7829 / D4) 문제이다.

[ 문제풀이 ]

종이에 써져 있는 약수들을 통해서, 원래의 숫자가 무엇인지 알아내야 하는 문제이다.

단, 1과 해당 숫자인 N은 적어놓지 않았다고 했다.

처음에는 어떻게 접근해야될지 감이 잘 오질 않았는데, 정말 단순하게 생각했고 그대로 구현했더니 정답을 받았다.

예를 들어서 N이 '8'이라고 가정해보자. 그럼 '8'의 약수는 [ 1 , 2 , 4 , 8 ] 인데, 1과 N은 적지 않는다고 했으니

[ 2 , 4 ] 만 적혀있을 것이다.

2 x 4 = 8 이다.

N이 '16'이라고 가정해보자. 그럼 '16'의 약수는 [ 1 , 2 , 4 , 8 , 16 ] 인데, 1과 N은 적지 않는다고 했으니

[ 2 , 4 , 8 ] 만 적혀있을 것이다.

2 x 8 = 16

4 x 4 = 16 이다.

마지막으로 한개만 더해보자.

N이 '20' 이라고 가정해보자. 그럼 '20'의 약수는 [ 1 , 2 , 4 , 5 , 10 , 20 ] 인데, 1과 N은 적지 않는다고 했으니

[ 2 , 4 , 5 , 10 ] 이 적혀있을 것이다.

2 x 10 = 20

4 x 5 = 20 이다.

위에서 봤듯이, 우리는 약수의 적절한 조합으로 N을 알아낼 수가 있다.

더 쉽게 이야기해서, 주어진 약수 리스트들 중에서, '최소값' 과 '최대값'을 찾아서 그 2개의 값을 곱해주면 N이 나오게 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int P, Answer;
int Min_Value, Max_Value;
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Min_Value = 987654321;
    Max_Value = 0;
}
 
void Input()
{
    cin >> P;
    for (int i = 0; i < P; i++)
    {
        int a; cin >> a;
        Min_Value = Min(Min_Value, a);
        Max_Value = Bigger(Max_Value, a);
    }
}
 
void Solution()
{
    Answer = Min_Value * Max_Value;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    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;
}