ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [λ°±μ€€] 15965 K번째 μ†Œμˆ˜ with Python
    PS 2022. 3. 4. 21:29
    728x90
    λ°˜μ‘ν˜•

    πŸ“Œ BOJ 15965 K번째 μ†Œμˆ˜

    πŸ’‘ 쑰건

    1. μ„œλΈŒνƒœμŠ€ν¬κ°€ μ‘΄μž¬ν•œλ‹€.
    2. 2 μ΄μƒμ˜ μžμ—°μˆ˜ N이 1κ³Ό N을 μ œμ™Έν•˜κ³  μ–΄λ–€ μžμ—°μˆ˜λ‘œλ„ λ‚˜λˆ„μ–΄ 떨어지지 μ•Šμ„ λ•Œ μ†Œμˆ˜λΌκ³  ν•œλ‹€.
    3. μžμ—°μˆ˜ Kκ°€ 주어진닀.(1 ≤ K ≤ 500,000)
    4. k번째 μ†Œμˆ˜λ₯Ό κ΅¬ν•˜λŠ” 문제
    5. μˆ˜ν•™, μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체 μœ ν˜•μ˜ 문제

    πŸ–₯ μ†ŒμŠ€ μ½”λ“œ

    BIG_NUM = 10**7
    
    k = int(input())
    array = [1 for _ in range(BIG_NUM + 1)]
    
    answer = []
    for i in range(2, BIG_NUM + 1):
        if array[i]:
            answer.append(i)
            for j in range(i+i, BIG_NUM + 1, i):
                array[j] = 0
    
    print(answer[k - 1])

    πŸ”– 예제 및 μ‹€ν–‰κ²°κ³Ό

    예제

    3

    μ‹€ν–‰κ²°κ³Ό

    5

    ⌨️ 문제 풀이

    1. μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체λ₯Ό μ‚¬μš©ν•˜μ—¬ 풀이λ₯Ό ν•˜λ©΄ λ©λ‹ˆλ‹€.
    2. i κ°€ μ†Œμˆ˜μΌ λ•Œ, i의 λ°°μˆ˜λŠ” μ†Œμˆ˜κ°€ μ•„λ‹ˆλ‹€ λΌλŠ” μ•„μ΄λ””μ–΄μ—μ„œ μ‹œμž‘μ„ ν•©λ‹ˆλ‹€.
    3. iκ°€ μ†Œμˆ˜λ‘œ νŒλ³„μ΄ λ˜μ—ˆλ‹€λ©΄, 10^7 κΉŒμ§€ 검사λ₯Ό ν•˜λ©΄μ„œ i의 λ°°μˆ˜λŠ” λͺ¨λ‘ array λ°°μ—΄μ—μ„œ 0으둜 μ²΄ν¬ν•©λ‹ˆλ‹€.
    4. μ†Œμˆ˜λ‘œ νŒλ³„λœ iλŠ” answer에 μΆ”κ°€ν•΄μ€λ‹ˆλ‹€.

    πŸ’Ύ λŠλ‚€μ 

    1. μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체가 μ΅μˆ™ν•˜μ§€ μ•Šμ€ μƒνƒœμ—μ„œ ν’€μ—ˆμ—ˆλ˜ λ¬Έμ œμ˜€λ‹€.
    2. μ§€κΈˆμ€ 문제λ₯Ό μŠ₯ μ½μœΌλ‹ˆ λ°”λ‘œ 풀이가 생각이 났닀.
    λ°˜μ‘ν˜•

    λŒ“κΈ€

Designed by Tistory.