[백준] 1095번 파이썬 - 마법의 구슬

s+f개의 구슬 중 s개를 뽑는 조합의 개수를 구하고

그 개수를 m이하의 사람들에게 모두 같은 개수로 나누어 주면 되는데

이 때 m의 값이 최대여야 한다.

첫 번째 코드

# 1,000,000,000범위 -> 시간복잡도 O(N)
import math

s,f,m = map(int,input().split())
answer = -1

# 1. s+f개로 만들 수 있는 조합의 개수 구하기 -> math.comb 시간복잡도 O(logn)
combs = math.comb(s+f,s)

# 2. m 이하의 사람들이 모두 같은 개수의 조합을 테스트 할 수 있도록 나누기
if combs <= m:
    answer = combs
# 조합의 수가 m보다 클 때만 고려해주면됨
else:
    for i in range(m,0,-1):
        if combs%i == 0:
            answer = i
            break
print(answer)

시간초과

 

 

두 번째 코드

# 1,000,000,000범위 -> 시간복잡도 O(N)
import sys
import math

input = sys.stdin.readline
s,f,m = map(int,input().split())
answer = 1

def CountPeople(s,f,m):
    # 1. s+f개로 만들 수 있는 조합의 개수 구하기 -> math.comb 시간복잡도 O(logn)
    combs = math.comb(s+f,s)
    
    left = 1
    right = m

    while left <= right:
        mid = (left+right) // 2
        if combs % mid == 0:
            answer = mid
            # 우리는 최대값을 구해야 하므로 mid보다 작은 수들은 볼 필요 없음
            left = mid + 1
        else:
            if combs % right == 0:
                answer = right
                return answer
            elif combs % left == 0:
                left += 1
            else:
                right -= 1

if m > 1:
    answer = CountPeople(s,f,m)
    print(answer)
else:
    print(-1)

 

이진탐색 비스무리하게 풀어보았다

이것도 시간초과 ㅎ  sys 임포트해도 시간초과 pypy3으로 내도 시간초과 온세상이 시간초과 ㅎ

 

정답 코드

chat gpt가 math.comb 시간복잡도 O(logn)이라고 거짓말했다.다시 물어보니까 O(n)이라고 했다...

나쁜놈

갓유록 매니저님이 푸시고 공유해주셨다...

 

아이디어는 조합값을 계산하지 않는 것!

1. m의 범위 내에서 소수를 찾고

2. 1번의 소수들로 입력 값들을 소인수분해한다

3. 소인수분해된 수들의 지수를 구하고 ( 지수 = 소수의 등장 횟수)

4. 입력값 m부터 1까지 역순으로 탐색하면서 (최댓값을 구하는 것이므로)

    각각의 입력값을 소인수분해 & 지수 값을 비교한다

5. 입력값의 지수 값이 해당 소수의 지수값보다 크거나 같으면

    -> 조건을 만족하는 약수이고, 가장 먼저 나온 조건을 만족하는 약수가 정답이다

    (m값을 역순으로 탐색하기 때문)

 

자세한 설명은 주석으로 적혀있음제출은 꼭 pypy3으로 해야 시간초과가 안난다

import sys
input =sys.stdin.readline
# 아이디어 -> 직접 조합 값을 계산하지 않고, 
# 소인수분해하여 소수의 지수 값을 구한 후에, 
# 해당 소수들의 지수 값들을 이용하여 가장 큰 약수를 구한다!

# 소인수분해 / 지수 구하는 함수 -> 소수 pn이 num에 몇번 나타나는지 구하는 함수이다
def cal(pn,num):
    tmp = num
    # pn의 지수 저장할 변수 d
    d = 0
    # tmp//소수 pn이 양수이면
    while tmp // pn > 0:
        # 나눠주기
        tmp //= pn
        # 지수 +1
        d += tmp
    return d

s, f, m = map(int, input().split())
# 소수
prime = []
# 소수의 지수
cnt = []

# dp 인덱스 설정 - m값 10만
b = 1000000
dp = [True] * (b+1)
# 0,1은 소수가 아님
dp[0] = False
dp[1] = False

# 에라토스테네스의 채 사용 - m의 범위 내에서 소수 찾기
for k in range(2, int(b**0.5) + 1):
    if dp[k] == True:
        # 제곱한 수들 -> 소수가 아님 -> false처리
        for i in range(k*k, b+1, k):
            dp[i] = False

# dp의 범위 내에서
for i in range(b+1):
    # dp[i] = true인 수들, 즉 i가 소수이면
    if dp[i]:
        # 소수 리스트 prime에 i 추가
        prime.append(i)
        # i의 지수 구해서 소수지수 리스트 cnt에 추가 -> cal(i, s+f)는 조합식 "(s+f)!"에서 소수 i의 지수를 구하는 함수. 나머지도 동일
        cnt.append(cal(i,s+f)-cal(i,s)-cal(i,f))

# 다음과 같은 과정이 끝나면 cnt에 소수의 지수들이 남는다

ans = 1
# m부터 1까지 역순으로 돈다
for i in range(m, 0, -1):
    tmp = i
    flag = True
    # 소수 길이만큼 돈다
    for j in range(len(prime)):
        count = 0
        # tmp는 현재 m의 값. 현재 m의 값이 현재 소수 값으로 나누어 떨어지면 tmp갱신 & 지수 값 +=1
        while tmp % prime[j] == 0:
            tmp //= prime[j]
            count += 1
        # count가 해당 소수의 지수보다 크면 => 반복문 종료
        if count > cnt[j]:
            flag = False
            break
    # 반복문을 다 돌았을 때 flag가 true면 현재 탐색중인 i명이 조건 만족 -> for문은 역순으로 도므로 i가 정답이다. 고로 break
    if flag:
        ans = i
        break

print(ans)