[BOJ 2501] 약수 구하기 (파이썬)

 

안녕하세요.

오늘은 백준 문제 중에서 간단한 문제를 소개해드리려고 합니다.

문제의 출처는 다음과 같습니다.

https://www.acmicpc.net/problem/2501 

2501번: 약수 구하기

 

1. 문제

 

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

 

2. 입력

 

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

 

3. 출력

 

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

 

4. 소스코드 (파이썬)

 

 

5. 풀이방법

 

우선 N과 K를 input으로 받은 다음에 map과 int함수를 이용하여 정수값으로 만들어 줍니다.

 

저는 리스트를 생성하여 문제풀이에 접근을 하였습니다. 

 

그 다음 for문을 돌면서, 나눴을 때 나머지가 0이 되는 수(약수)들을 리스트에 추가시킵니다. 

따라서 num_list에는 N의 약수들이 저장되게 됩니다.

예를들어 N으로 6이 들어온다면  num_list=[1,2,3,6] 으로 저장됩니다.

 

N의 약수들의 개수가 K보다 크거나 같으면 값을 정상적으로 출력해주면 됩니다. 값을 출력할 때 리스트는 0번 인덱스부터 시작하므로 k가 아닌 k-1의 인덱스로 접근을 해야 원하는 값이 나오게 됩니다.

 

반대로 N의 약수들의 개수가 K보다 작다면 0을 출력해주도록 합니다.

 

6. 결과