[백준] 1037번: 약수

링크: www.acmicpc.net/problem/1037

약수

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

---

 

진짜 약수는 1과 자신을 제외한 나머지 약수들을 뜻한다.

 

접근을 어떻게 해야되나 고민을 해보았는데, 그냥 진짜약수를 입력으로 받아오면 가운데 숫자를 곱해주면 될거 같았다. 여기서 또 고려해야되는 것이 진짜 약수들의 개수가 홀수와 짝수일때, if문으로 나눠주어서 문제를 해결하였다.

 

아래는 코드이다.

"""
백준 알고리즘 1037번: 약수
https://www.acmicpc.net/problem/1037
"""
import sys

def calc(n, realYakSu):
    realYakSu.sort() # 오름 차순으로 정렬 시킨다.
    if n%2 == 0:
        # 약수의 개수가 짝수이면 가운데 2개의 약수의곱을 리턴
        # ex) 20= 2, 4*, 5*, 10
        return realYakSu[int(n/2)] * realYakSu[int(n/2) -1]
    else:
        # 약수의 개수가 홀수이면 가운데 1개의 약수의 제곱을 리턴
        # ex) 16= 2, 4*, 8
        return realYakSu[int(n/2)]**2


def main():
    n = sys.stdin.readline()
    n = int(n)

    realYakSu = sys.stdin.readline().split()
    realYakSu = [int(yaksu) for yaksu in realYakSu]

    print(calc(n, realYakSu))

if __name__ == "__main__":
    main()

코드의 주석에서 처럼 예시를 들어보자

20의 경우 입력은 "4,  4,2,5,10" 정도 될것이다. 입력을 받고 오름차순으로 정렬한다음 2,4,5,10이되면 가운데 두 수를 뽑아 곱해준다.

반면 16의 경우 입력은 "3,  4,2,8"이 될것이다. 그렇다면 가운데 수를 제곱해서 값을 얻어오면 된다.

 

---

근데 글을 쓰면서 간단하게 줄일 수 있을거 같다. 약수의 개수를 홀수와 짝수일 때로 나누지 않고 그냥 정렬한다음 양 끝의 수를 곱해주면 될거 같다. 바로 코드를 작성해보면....

"""
백준 알고리즘 1037번: 약수
https://www.acmicpc.net/problem/1037
"""
import sys

def calc(n, realYakSu):
    realYakSu.sort() # 오름 차순으로 정렬 시킨다.
    return realYakSu[0] * realYakSu[n-1]


def main():
    n = sys.stdin.readline()
    n = int(n)

    realYakSu = sys.stdin.readline().split()
    realYakSu = [int(yaksu) for yaksu in realYakSu]

    print(calc(n, realYakSu))

if __name__ == "__main__":
    main()

코드가 확 줄었다... 왜 지금에서야 생각난거냐구... 해당 코드가 위에서 작성한 코드보다 훨씬더 직관적이고 보기 편하다.