say repository

import sys
import heapq
n, k = map(int,sys.stdin.readline().split())
q = [] # 보석 최소힙
bag = [] #가방 무게 리스트
for _ in range(n):
    heapq.heappush(q,list(map(int,sys.stdin.readline().split())))
for _ in range(k):
    bag.append(int(sys.stdin.readline()))
# 가방 오름차순 정렬
bag.sort()

result = 0
take = [] # 담은거
for c in bag:
    # 가방에 담을 수 있는 무게만 최대힙에 넣기
    while q and q[0][0] <= c:
        possible_m, possible_v = heapq.heappop(q)
        heapq.heappush(take, -possible_v)

    if take:
        result += (-heapq.heappop(take))
    elif not q:
        break
print(result)

import sys
import heapq
n = int(sys.stdin.readline())
q = []
for _ in range(n):
    heapq.heappush(q,list(map(int,sys.stdin.readline().split())))
    # 최소힙에 삽입
target, fuel = map(int,sys.stdin.readline().split())

move = [] #움직인 큐 최대힙
cnt = 0
while fuel<target:
    while q and q[0][0]<=fuel:
        mf, pf = heapq.heappop(q)
        heapq.heappush(move,[-pf,mf])

    if not move:
        cnt = -1
        break
    pf1, mf1 = heapq.heappop(move)
    fuel += -pf1
    cnt += 1
print(cnt)

풀이

그리디 알고리즘, 우선순위 큐

1km를 가는데 1L의 연료가 새 나가게 되니까 처음의 연료양으로 최종 마을까지 가야 한다.

1. 입력받은 주유소 n개의 ( 주유소 거리, 연료 양 )을 최소 힙에 저장한다.
2. 처음의 연료 양을 시작으로 최종 마을까지 최소의 주유소를 거쳐 가야 한다.
3. 가는 길에 주유소가 있어야 하고 갈 수 있는 주유소에서 최대의 연료 양을 뽑아야 한다.
4. 이때, 우선순위 큐를 생각하여 최대 힙으로 바꿔야 한다.
5. 그중에서도 연료 양이 기준이 되기에 (연료 양, 주유소 거리) 순서를 바꿔주고 ( - 연료양, 주유소거리 )로 연료 양에 -를 붙여서 최대 힙을 만든다. 

출처 : 백준

문제

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x<p, y<q 이다. 예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다. 

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

그림 (a)

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다. 

그림 (b)

그림 (c)

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

그림 (d)

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다. 

공통부분의 특성코드 문자

직사각형	a
선분	b
점	c
공통부분이 없음	d

코드1

#2527
import sys
for i in range(4):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int,sys.stdin.readline().split())
    # 직사각형이 겹치기 위한 계산
    # 왼쪽 변
    xl = max(x1, x3)
    # 오른쪽 변
    xr = min(x2, x4)
    # 윗 변
    upr = min(y2,y4)
    # 아랫 변
    downl = max(y1, y3)

    #겹치는 부분 (차이)
    diffx = xr-xl
    diffy = upr-downl

    # 차이가 둘다 양수면 겹치는 부분이 직사각형
    if diffx > 0 and diffy > 0:
        print("a")
    # 둘 다 0이면 점
    elif diffx == 0 and diffy == 0:
        print("c")
    # 공통부분이 없음
    elif diffx < 0 or diffy < 0:
        print("d")
    else: # 선분
        print("b")

코드2

#2527
import sys
for i in range(4):
    x1, y1, p1, q1, x2, y2, p2, q2 = map(int,sys.stdin.readline().split())

    if p1 < x2 or q1 < y2 or p2 < x1 or q2 < y1:
        #겹치지 않음
        print("d")
        continue
    elif p1 == x2 or p2 == x1:
        if q1 == y2 or q2 == y1:
            print("c") #점
            continue
        else:
            print("b") #선분
            continue
    elif q1 == y2 or q2 == y1:
        print("b")
        continue
    else:
        print("a") #직사각형
        continue

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

import sys
from collections import deque

dx = [1,2,2,1,-1,-2,-2,-1]
dy = [2,1,-1,-2,-2,-1,1,2]
def bfs(sx, sy, ex, ey):
    q = deque()
    q. append((sx, sy))
    chess[sx][sy] = 1
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(chess[x][y]-1)
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and chess[nx][ny] == 0:
                chess[nx][ny] = chess[x][y] + 1
                q.append((nx,ny))

T = int(sys.stdin.readline())
for i in range(T):
    n = int(sys.stdin.readline()) #체스판 한 변
    sx, sy = map(int,sys.stdin.readline().split())
    ex, ey = map(int,sys.stdin.readline().split())
    #체스판 생성
    chess = [[0]*n for _ in range(n)]
    bfs(sx, sy, ex, ey)

풀이

bfs로 처음 좌표부터 시작해서 끝 좌표에 도착할때까지 1을 더해주며 이동 횟수를 체스판에 저장한다.

처음 좌표를 1로 바꾸고 시작하므로 최종 횟수에서 1을 빼준다.

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

#7569
import sys
from collections import deque
m, n, h = map(int,sys.stdin.readline().split())
tomato = [[list(map(int,sys.stdin.readline().split())) for _ in range(n)] for _ in range(h)]
# print(tomato)

dx = [-1, 0, 1, 0, 0, 0]
dy = [0, 1, 0, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
q = deque()
# 익은 토마토 좌표 큐에 넣기
for z in range(h):
    for i in range(n):
        for j in range(m):
            if tomato[z][i][j] == 1:
                q.append((z,i,j))
def bfs():
    while q:
        z, x, y = q.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h and tomato[nz][nx][ny] == 0:
                tomato[nz][nx][ny] = tomato[z][x][y] + 1
                q.append((nz,nx,ny))

result = 0 #처음부터 모두 익은 상태
bfs()
for z in range(h):
    for i in range(n):
        for j in range(m):
            if tomato[z][i][j] == 0: #모두 익지 못함
                print(-1)
                sys.exit(0) #종료
            result = max(result,tomato[z][i][j]) #모두 익는 날짜 or 0 중 가장 큰 것 답
print(result-1) #처음에 익은 토마토부터 시작해서 1일 빼줘야함.

풀이

토마토 문제랑 똑같은데 3차원 배열인 부분만 다르다.

3차원 배열 주의하자.

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

#7576
import sys
from collections import deque
m, n = map(int,sys.stdin.readline().split())
tomato = [[]*m for _ in range(n)]
for i in range(n):
    tomato[i] = list(map(int,sys.stdin.readline().split()))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque()
# 익은 토마토 좌표 큐에 넣기
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i,j))
def bfs():
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[x][y] + 1
                q.append((nx,ny))

result = 0 #처음부터 모두 익은 상태
bfs()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0: #모두 익지 못함
            print(-1)
            sys.exit(0) #종료
        result = max(result,tomato[i][j]) #모두 익는 날짜 or 0 중 가장 큰 것 답
print(result-1) #처음에 익은 토마토부터 시작해서 1일 빼줘야함.

풀이

bfs로 풀이했다.

익은 토마토 (1) 의 좌표를 큐에 넣고 익은 토마토 상하좌우에 안익은 토마토(0)을 찾아서 bfs을 진행한다.

bfs 진행하면서 전의 값에 + 1 을 해준다.

bfs 완료하고 좌표에 안익은 토마토(0) 이 있으면 -1 출력하고 종료한다.

없으면 처음부터 모두 익었거나 (정답 0) 시간이 지나서 익은 것이다.

둘 중 더 큰 값이 답이다.

여기서 마지막에 result-1 을 해주는 이유는 익은 토마토에서 시작해서

처음의 값이 (bfs 함수 내에서 tomato[i][j]가 1)  1부터 시작한다. 

따라서 답을 구할 때 -1을 빼줘야한다.

출처 : 백준

#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) 소수인지 판별은 앞서 말했듯 에라토스테네스의 체 범위보다 크면 소수로 나눈다. 나누어지면 소수가 아니다.

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