K๋ฒ์งธ ์ฝ์
๐ ๋ฌธ์
์ด๋ค ์์ฐ์ 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๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
โฃ ์ ๋ ฅ์ค๋ช
์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค.
N์ 1 ์ด์ 10,000 ์ดํ์ด๋ค. K๋ 1 ์ด์ N ์ดํ์ด๋ค.
โฃ ์ถ๋ ฅ์ค๋ช
์ฒซ์งธ ์ค์ N์ ์ฝ์๋ค ์ค K๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ง์ผ N์ ์ฝ์์ ๊ฐ์๊ฐ K๊ฐ๋ณด๋ค ์ ์ด์ K๋ฒ์งธ ์ฝ์๊ฐ ์กด์ฌํ์ง ์์ ๊ฒฝ์ฐ์๋ -1์ ์ถ๋ ฅํ์์ค.
โฃ ์ ๋ ฅ์์
1 6 3
โฃ ์ถ๋ ฅ์์
1 3
๐ง ํ์ด
'''
[์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ ์
๋ฌธ]
K๋ฒ์งธ ์ฝ์
์ด๋ค ์์ฐ์ 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๋ฒ์งธ๋ก ์์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
'''
n, k = map(int, input().split()) # n, k ๊ฐ๊ฐ ์ ์ ํ ๋น
d_list = [] # ์ฝ์๋ฅผ ๋ด๊ธฐ ์ํ ๋น ๋ฆฌ์คํธ ํ ๋น
for i in range(1, n+1): # 1๋ถํฐ n๊น์ง ๋ฐ๋ณต
if n % i == 0: # i๋ก n์ด ๋๋ด์ ๋, ๋๋จธ์ง๊ฐ 0์ด๋ฉด
d_list.append(int(n // i)) # i๋ก n์ ๋๋ ๋ชซ์ d_list์ ์ถ๊ฐ
d_list.sort() # ์ฝ์ ๋ฆฌ์คํธ d_list ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
if len(d_list) >= k: # d_list์ ์ฝ์ ๊ฐฏ์๊ฐ k๋ณด๋ค ๋ง๊ฑฐ๋ ๊ฐ์ ๋,
print(d_list[k-1]) # d_list์ k-1๋ฒ์งธ ์ธ๋ฑ์ค์ ๊ฐ ์ถ๋ ฅ
else:
print(-1) # ๊ทธ๋ ์ง ์์ ๋๋ -1 ์ถ๋ ฅ
'๐งฉ Algorithm > ๐จ Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ] ์๋ฆฟ์์ ํฉ (0) | 2022.07.24 |
---|---|
[ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ] ์ ๋ค๋ฉด์ฒด (0) | 2022.07.24 |
[ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ] ๋ํ๊ฐ (0) | 2022.07.24 |
[ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ] K๋ฒ์งธ ํฐ ์ (0) | 2022.07.24 |
[ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ] K๋ฒ์งธ ์ (0) | 2022.07.24 |