Informatica Online Judge

  경곽이와 최소합 [0996 / 03E4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 94   Total Tried : 712


The Champion of this Problem (C++) : gs19047 - 0ms / 233byte
My Best Submission (C++) : N/A

[JeongHJ]

Background

경곽이는 n개의 양의 정수 x1, x2, ..., xn을 가지고 있다. 경곽이는 필요한 만큼 다음 연산을 반복 수행한다.

연산 과정
(1) xi > xj가 되는 두 개의 서로 다른 값을 선택한다.
(2) xi = xi – xj 수행한다.

목적은 가능한 경우의 연산을 수행한 결과 x1, x2, ..., xn의 합이 최소가 되도록 하는 것이다. 경곽이를 도와 최소의 합을 구하는 프로그램 작성하시오.

Input

첫 번째 줄에는 정수 n이 입력된다.
두 번째 줄부터는 n개의 x1, x2, ..., xn 이 입력된다.

[입력값의 정의역]
2 ≤ n ≤ 100
1 ≤ xi ≤ 100

Output

최소 합을 출력한다.

IO Example

입력 1
2
1 2

출력 1
2

입력 2
3
2 4 6

출력 2
6


입력 3
2
12 18

출력 3
12


입력 4
5
45 12 27 30 18

출력 4
15

Note
첫 번째 입력인 경우, x2=x2–x1로 x2=1이고 x1=1로 변경되므로 더 이상 xi > xj 인 쌍이 없으므로 x1+x2의 합은 2로 결과는 2가 된다.

두 번째 입력의 경우, x3=x3-2가 되면 x3=6-4=2로 x3=2가 되고 x2=4, x1=2가 된다. 그러면 x2=x2-x1이 가능하므로 x2=4-2=2가 된다. 그럼 x1=x2=x3=2가 되므로 마지막 x1,x2,x3의 합은 6이 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]