[백준] 4948, 15649_python

베르트랑 공준

4948번: 베르트랑 공준

• 코드

import math

arr = []
while True:
    n = int(input())
    if n==0:
        break
    arr.append(n)

# 입력 받은 값 중 가장 큰 값까지 에라토스테네스의 채로 소수 확인
arr_max = max(arr) 

temp = [0] * ((2*arr_max)+1)

for i in range(2, int(math.sqrt(2*arr_max))+1):
    k = 2
    while k * i <=2*arr_max:
        temp[k*i] = 1
        k+=1

for i in range(len(arr)):
    count = 0
    # 입력 받은 값마다 n+1 ~ 2n 범위에서 소수 개수 찾기
    for j in range(arr[i]+1,2*arr[i]+1):
        if temp[j] == 0:
            count+=1
    print(count)

• 풀이를 생각해낸 과정
  • 입력 받은 값 중 가장 큰 값을 기준으로 소수를 찾고, 입력 받은 값마다 입력 받은 값마다 n+1 ~ 2n 범위에서 소수 개수를 찾는다.
• 시간복잡도 계산
  • O(N2)

 

---

N과 M(1)

15649번: N과 M (1)

• 코드

from itertools import permutations
n,m = map(int,input().split())

temp = []
for i in permutations(range(1,n+1),m):
    temp = list(i)
    print(' '.join(str(s) for s in temp))

• 풀이를 생각해낸 과정
  • 파이썬 itertools 모듈의 permutations 함수를 활용하여 중복을 허용하지 않고 n개에서 m개를 뽑는다.
  • 출력 포맷을 맞추기 위해 숫자를 문자열로 바꾼뒤, join으로 출력한다.
• 시간복잡도 계산
  • O(N!)