[Python3] 백준 2501번 약수 구하기

try 2 times / 난이도 : ★★☆☆☆

문제 확인

2501번: 약수 구하기

코드 깃허브 확인

GitHub - yyeongeun/codingtest: 코딩테스트 공부

정답 해설

answer = []
N, k = map(int,input().split())

for i in range(1,N+1):
    if N % i == 0:
        answer.append(i)

answer.sort() # 이미 값은 sort되어있으므로 굳이 할 필요 없다. 

if len(answer) < k: # len(answer)를 변수로 지정해도 된다.
    result = 0  # 결과 값을 바로 print 해도 된다.
else:
    result = answer[k-1]

print(result)

 

공부한 내용

1. 약수 = 0 이상 해당 값 이하로 나눴을 때 나머지가 0인 수

 

2. 다른 코드 이해하기

1. 약수인 경우, k에 1을 빼주고 그 값이 0이 되었을 때 출력해주는 방법

n,k=map(int,input().split())
res=0
for i in range(1,n+1):
    if n%i==0:
        k-=1
        if k==0:
            res=i
print(res)

k번째 작은 약수만 구하는 것이므로 전체 약수를 다 구하지 않는 방법이다.

첫번째 약수가 나오면 k* = k-1

두번째 약수가 나오면 k** = k*-1 = k-1-1

이런 식으로 하면,

k번째 약수가 나오면 k***** = k-1*k (->1을 k번 빼준다)

그러므로 n을 i로 나눴을 때 k가 0이 된다면, 해당 i가 k번째 약수이다.

[백준]약수구하기/2501번/파이썬/Python/수학

 

2. 약수인 경우, 새 변수에 1을 더해주고 그 변수가 k가 되면 출력해주는 방법

N, K = map(int, input().split())
cnt = 0
for i in range(1, N+1):
    if N%i == 0:
        cnt += 1
        if cnt == K:
            print(i)
            break
if cnt < K:
    print(0)

새 변수명 = cnt

첫번째 약수가 나오면 cnt* = cnt+1

두번째 약수가 나오면 cnt** = cnt*+1 = cnt+1+1

이런 식으로 하면,

k번째 약수가 나오면 cnt***** = cnt+1*k (->1을 k번 더해준다)

그러므로 n을 i로 나눴을 때 cnt가 k이 된다면, 해당 i가 k번째 약수이다.

k번째 약수를 찾으면 if문을 break해준다.

백준 알고리즘 2501번 약수 구하기(python)