Tag: greedy algorithm

import heapq

N = int(input())

lessons = []
for _ in range(N):
    i, s, e = map(int, input().split())
    lessons.append((s, e, i - 1))

lessons.sort()
room_end = [(lessons[0][1], 1)]
result = [0] * N
result[lessons[0][-1]] = 1
room_cnt = 1

for s, e, i in lessons[1:]:
    # 가장 일찍 끝나는 방
    min_end, room_i = heapq.heappop(room_end)
    # 그 방을 사용 가능할 경우
    if min_end <= s:
        heapq.heappush(room_end, (e, room_i))
        result[i] = room_i
    # 사용 못하는 경우 -> 새로운 방
    else:
        # 원래대로 복구
        heapq.heappush(room_end, (min_end, room_i))
        # 새로운 방 만들기
        room_cnt += 1
        result[i] = room_cnt
        heapq.heappush(room_end, (e, room_cnt))

print(room_cnt)
print(*result, sep='\n')

MAX_W = 1000
N, M = map(int, input().split())

if N != 0:
    books = list(map(int, input().split()))
    cnt = 1
    remain_w = M
    for book in books:
        # 더 넣을 수 없으면 포장
        if remain_w < book:
            cnt += 1
            remain_w = M
        remain_w -= book

    print(cnt)
else:
    print(0)

test_case = int(input())


# 제한 칼로리 내에서 최대의 맛
def search_best(hamburgers, sum_cal=0, sum_score=0):
    global max_score
    max_score = max(max_score, sum_score)

    for i, (score, cal) in enumerate(hamburgers):
        if sum_cal + cal > l:
            continue
        search_best(hamburgers[i + 1:], sum_cal + cal, sum_score + score)


for t in range(test_case):
    n, l = map(int, input().split())

    hamburgers = [list(map(int, input().split())) for _ in range(n)]

    max_score = 0

    search_best(hamburgers)

    print(f"#{t + 1} {max_score}")

rope = []
for i in range(0, n):
    rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0
for cnt, r in enumerate(rope):
    if max_w <= r * (cnt + 1):
        max_w = r * (cnt + 1)

print(max_w)

반복문을 돌면서 (로프의 개수) * (지금 확인한 로프의 무게)의 값이 저장해 놨던 무게 max_w 보다 크면 max_w를 바꿔준다.

dynamic programing으로 접근해 보면 조약돌의 오른쪽에서 작업을 시작하여 각 자리마다 그 때의 최소 작업 횟수를 저장하여 memoization할 수 있다.

하지만 단순히 이전까지의 최소 작업 횟수에 현재 자리의 최소 작업을 더한다고 최종적인 최소 작업 횟수가 될 수는 없다. 아래와 같은 예를 보자.

조약돌의 개수가 위와 같이 주어졌을 경우 두 번째 자리까지 최소 횟수는 2이다. 이를 저장하고 다음으로 넘어가서 마지막 자리인 두 개의 조약돌을 빼내는 횟수 1을 단순히 더하면 총 횟수는 3회이다.

하지만 처음부터 1번 작업으로 모두 진행하게 되면 두 번 만에 끝낼 수 있다.

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    num = int(input())
    pq.put(num)

result = 0

while pq.qsize() > 1:
    tmp = pq.get()
    num = pq.get()
    result += tmp + num
    pq.put(tmp + num)

print(result)

우선순위 큐에 입력으로 들어온 카드 뭉치의 크기를 삽입하고 반복문을 시작한다.

우선순위 큐의 첫 번째, 두 번째 원소를 빼내서 더해준다 (카드 뭉치를 합침). 그리고 이를 결과가 저장될 result 함수에 저장해준다 (합칠 때 비교한 횟수를 반영). 마지막으로 첫 번째와 두 번째 원소의 합을 다시 우선순위 큐에 넣어준다. 다시 넣어주면 합쳐진 카드 뭉치를 자연스럽게 다시 합칠 수 있다.

| 1 | 4 | | 6 | 1 | | 2 | 5 | | 4 | 2 | | 3 | 6 | | 7 | 3 | | 4 | 2 | | 1 | 4 | | 5 | 7 | | 2 | 5 | | 6 | 1 | | 3 | 6 | | 7 | 3 | | 5 | 7 |

여기서 첫 번째 리스트(성적 순)는 면접 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set(p_cnt[1:top2 + 1])

반대로 두 번째 리스트(면접 순)는 성적 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set2 = set(p_cnt2[1:top1 + 1])

이렇게 만들면 각 set에 한 분야의 1 순위인 사람보다 다른 분야의 순위가 높은 사람들을 걸러낼 수 있고, 이 둘의 교집합을 이용하면 두 분야의 1 순위인 사람들보다 적어도 하나의 분야의 순위가 높은 사람들을 추려낼 수 있어서 정답을 구할 수 있다고 생각했다.

예를 들면 55-50+40+90-100+10-11 이라는 수식이 입력됐을 때 55-(50+40+90)-(100+10)-11 = 55-50-40-90-100-10-11 로 만들 수 있다.

st = input().strip()+ '+'
total = 0
minus = False
num = ''
for c in st:
    if c.isdigit():
        num += c
    else:
        if minus:
            total -= int(num)
        else:
            total += int(num)
        if c == '-':
            minus = True
            
        num = ''
print(total)

입력은 숫자와 부호가 섞인 문자열로 주어지기 때문에 그 문자열을 확인하면서 문자가 숫자인지 부호인지에 때라 다르게 처리를 해주어야 한다.

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 $2^31-1$보다 작거나 같은 자연수 또는 0이다.

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

끝나는 시간을 기준으로 먼저 정렬하고 같으면 시작하는 시간을 기준으로 정렬하는 것이 핵심이다.

이렇게 정렬을 하게 되면 항상 그 시간에 시작하는 회의 중 가장 빨리 끝나는 회의를 선택할 수 있으며, 끝나는 시간 이후에 시작하는 회의 중 가장 빨리 끝나는 회의도 바로 선택할 수 있다.

n = int(input())
meetings = []

for _ in range(n):
    s, f = map(int, input().split())
    meetings.append((s, f))

meetings.sort(key=lambda x: (x[1], x[0]))

cur = 0
cnt = 0
for s, f in meetings:
    if cur <= s:
        cur = f
        cnt += 1
print(cnt)