say repository

#15711
import sys

# 에라토스테네스의 체
# n = 2*(10**12) +1 # 끈의 길이 메모리 초과 따라서 절반만 에라토스테네스의 체 수행
n = 2*(10**6) + 1
arr = [True for _ in range(n)]
primes = [] # 소수
for i in range(2,n):
    if arr[i]:
        primes.append(i)
        for j in range(2*i, n, i):
            arr[j] = False

# 소수인지 판별
def isPrime(x):
    if x > n: # x 가 n인 2*10**12 보다 크면
        for prime in primes:
            if prime >= x:
                break
            elif x % prime == 0:# 소수로 나뉘는지로 판별
                return False
        return True
    else: # x가 n보다 작으면 바로 소수에서 꺼내기
        return arr[x]

# 테스트케이스
t = int(sys.stdin.readline())
for _ in range(t):
    ab = sum(map(int,sys.stdin.readline().split()))

    # 골드바흐의 추측 : 4보다 큰 짝수는 두 홀수 소수의 합으로 가능하다.
    # 4 보다 작으면 NO
    if ab < 4 :
        print("NO")
    # 4보다 큰 짝수 YES
    elif ab % 2 == 0:
        print("YES")
    else: # 홀수는 2(짝수 소수) + 홀수 소수의 합으로 가능하다. -> 홀수-2 가 소수인지 확인
        if isPrime(ab-2):
            print("YES")
        else:
            print("NO")

풀이

간단하게 에라토스테네스의 체로만 풀면 시간초과 난다.

문제에서 알고 있어야 할 것이 에라토스테네스의 체와 골드바흐의 추측이다.

근데 이렇게 풀어도 python으로는 시간초과가 나서 pypy3로 제출했다.

빠르게 풀 수 있는 방법 아시는분?

1) 체의 범위가 2*10**12나 되기 때문에 그 절반만 에라토스테네스의 체를 우선적으로 만들어주고

소수판별을 원하는 수가 이 범위보다 크면 소수로 나뉘는지로 판별한다.

2) 골드바흐의 추측 :  4보다 큰 짝수는 두 홀수인 소수의 합으로 가능하다.

따라서 4보다 작으면 NO 크면 짝수면 YES

4보다 큰 홀수는 2와 다른 소수 홀수의 합으로 이루어진다. 

따라서 홀수-2가 소수인지만 판별하면 된다.

3) 소수인지 판별은 앞서 말했듯 에라토스테네스의 체 범위보다 크면 소수로 나눈다. 나누어지면 소수가 아니다.

그 범위보다 작으면 바로 에라토스테네스의 체로 구해놓은 소수배열에서 꺼내쓴다.

#11053
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
d = [0]*n

for i in range(n):
    for j in range(i):
        if a[j] < a[i] and d[j] > d[i]:
            d[i] = d[j]
    d[i] += 1
print(max(d))

풀이

A = {10, 20, 10, 30, 20, 50} 로 경우의 수를 나눠서 구해보면 된다.

반복문을 돌면서, 자기 자신보다 작은 수열 중 가장 길이가 긴 수열의 크기 +1

 if a[i]>a[j]  -> 자기 자신보다 작은 수열

and d[j] > d[i] -> 가장 길이가 긴 수열의 크기

#2156
import sys
n = int(sys.stdin.readline())
arr = [0]*10000 #포도주
for i in range(n):
    arr[i] = int(sys.stdin.readline())

#dp테이블
#dp[i] = 0부터 i번째 포도주까지 최대로 마신 양
dp = [0] * 10000
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2], dp[1])

for i in range(3,n):
    dp[i] = max(dp[i-2]+arr[i], arr[i-1]+arr[i]+dp[i-3], dp[i-1])
print(max(dp))

풀이

다이나믹 프로그래밍이다.

dp[i] 는 처음부터 i번째까지 최대한 마신 포도주의 양이다.

dp[0] 부터 계산하면 점화식이 나오고 계산한다.

그 중 가장 큰 값을 출력하면 된다.

출처 : 백준

import sys
import heapq
n = int(sys.stdin.readline())
left_heap = [] #최대힙
right_heap = [] #최소힙
for _ in range(n):
    num = int(sys.stdin.readline())
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap,-num)
    else:
        heapq.heappush(right_heap,num)

    if len(left_heap)>=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]:
        #중간값이 중간값이 아니면
        l_value = -heapq.heappop(left_heap)
        r_value = heapq.heappop(right_heap)

        heapq.heappush(left_heap,-r_value)
        heapq.heappush(right_heap,l_value)
    print(-left_heap[0])

풀이

우선순위 큐를 사용해서 풀어야겠다는 생각까지는 했지만 시간초과가 났다.

다른 사람의 풀이들을 찾아보고 공부했다.

최대힙, 최소힙 모두 사용해야한다.

최대힙 : 중간 값 보다 작은 값들을 삽입한다. (내림차순 정렬)

최소힙 : 중간값보다 큰 값들을 삽입한다. (오름차순 정렬)

이 두가지만 생각하고 풀면 최대힙의 첫번째 원소값이 결국 배열의 중간값이 된다.

최대힙을 left_heap

최소힙을 right_heap으로 뒀다.

1) left_heap에 먼저 삽입

2) 다음, right_heap에 삽입 

3) 둘 다 원소가 있고  중간 값보다 더 큰 값이 left_heap[0]에 있을때.... 

len(left_heap) >=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]: 

-left_heap[0] , right_heap[0] 이 값을 서로 부호와 원소를 바꿔준다.

right_heap에 있는 모든 수는 left_heap에 있는 수보다는 커야한다. (중간값이 left_heap[0]에 있으니까!!!! )

4) 중간값 출력 left_heap[0]

import sys
n,c = map(int,sys.stdin.readline().split())
house = []
for _ in range(n):
    house.append(int(sys.stdin.readline()))
#집 오름차순 정렬
house.sort()
start = 1
end = house[-1]-house[0] #집 좌표 차이 최댓값
result = 0
while start<=end:
    mid = (start+end) // 2
    #처음 집부터 공유기 설치
    now = house[0]
    cnt = 1

    for i in range(1,len(house)):
        if house[i] >= now + mid:
            #공유기 설치
            cnt+=1
            now = house[i]
    #공유기 개수가 c가 되어야 한다.
    if cnt >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)

풀이

집 좌표가 10억이 넘어서 이분탐색으로 풀이해야 시간 초과가 나지 않는다.

집 좌표 차이가 중요하므로 오름차순으로 정렬하고 탐색을 시작한다.

start = 1 , end = 마지막 원소 - 첫번째 원소  ( 하면 가장 큰 차이의 좌표 차가 나온다.)

이분 탐색을 진행한다.

1. 설치된 공유기 수가 c보다 작으면  - 공유기를 더 설치해야 한다. end = mid-1
2. 설치된 공유기 수가 c보다 크거나 같다면 - 공유기를 덜 설치해야한다. start = mid+1

출처 : 백준

import sys
import heapq
n = int(sys.stdin.readline())
q = []
for i in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        #배열에서 가장 작은 값 출력 없으면 0
        if len(q)==0:
            print(0)
        else:
            print(heapq.heappop(q)[1])
    else:
        #배열에 x값 넣기
        heapq.heappush(q,(abs(x),x))

풀이

우선순위 큐를 사용한다.

절댓값이 작은 수 먼저 출력, 절댓값이 같은 수가 여러 개면 값이 작은 수 출력. 

이를 봐서 (abs(x),x) 튜플 형태로 절댓값과 수를 함께 우선순위 큐에 삽입한다.

우선순위 큐는 디폴트로 튜플의 첫 번째 값인 절댓값 기준으로 정렬된다.

import sys
input = sys.stdin.readline
n = int(input())
money = list(map(int,input().split()))
m = int(input())

start,end = 0,max(money)

while start<=end:
    mid = (start+end)//2 #상한액
    num = 0
    for i in money:
        # 상한액보다 요청 금액이 크면 상한액 배정
        if i >= mid:
            num += mid
        else: #아니면 요청 금액 배정
            num += i
    # 배정금액이 총 예산보다 작으면
    if num <= m:
        start = mid + 1
    else:
        end = mid -1
print(end)

풀이

특정 정수 상한액을 정하고 계산해야한다는 부분에서 이분 탐색을 해야 한다고 결론지었다.

start = 0, end = max(요청 금액)

mid = (start+end)//2

start<=end 가 될 때까지 이분 탐색을 반복하자.