[백준] 2847, 1439, 11000, 15903 (파이썬)

그리디에 관한 문제집 하나를 거의 다 풀었다. 하지만 아직 모자라다는 느낌이 강하다. 다른 적당한 문제집을 하나 골라서 추가적으로 풀어야할 것 같다. 오늘 문제 중에서 엄청나게 어렵다는 느낌을 받은 문제는 없었으나 한가지 문제에서 궁금증이 생겼다. 11000번 강의실 배정 문제인데 1931번 회의실 배정 문제와 유사하나, 필요없는 강의시간을 버리는 것이 아니라 heap에 저장해야한다. 여기서 나는 처음에 자체적으로 heap을 구현했으나 계속 틀렸다는 답을 얻었고 heapq모듈을 사용하고나서야 해결할 수 있었다. 이에 대한 이유를 찾아보고 있고 질문도 올렸다. 나중에 해답을 찾게된다면 업로드 하겠다.

백준 2847번 게임을 만든 동준이

import sys
T = int(sys.stdin.readline())
num_lst = list()
for _ in range(T):
    num_lst.append(int(sys.stdin.readline()))
count = 0
for i in range(len(num_lst)-1,0,-1):
    if num_lst[i-1]>=num_lst[i]:
        cha = num_lst[i-1]-num_lst[i]+1
        num_lst[i-1] -= cha
        count += cha
print(count)

백준 1439번 뒤집기

import sys
S = sys.stdin.readline().rstrip()
sum = 0
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        sum +=1
print((sum+1)//2)

백준 11000번 강의실 배정

# 1931 회의실 문제와 비슷하지만 heap을 사용하여 해결해야한다.
# heap에 관한 알고리즘만 참고하였다.
import sys
import heapq
N = int(sys.stdin.readline())
Time = []
heap = []
for _ in range(N):
    S,T = map(int,sys.stdin.readline().split())
    Time.append([S,T])
Time = sorted(Time,key=lambda x:(x[0],x[1]))
heapq.heappush(heap,Time[0][1])
for i in range(1,N):
    if Time[i][0] < heap[0]:
        heapq.heappush(heap,Time[i][1])
    else:
        heapq.heappop(heap)
        heapq.heappush(heap,Time[i][1])
print(len(heap))
'''
틀렸다고 뜬 코드, 이유는 계속 찾아봐도 모르겠어서 질문 창에 올렸다.
import sys
N = int(sys.stdin.readline())
Time = []
heap = []
for _ in range(N):
    S,T = map(int,sys.stdin.readline().split())
    Time.append([S,T])
Time = sorted(Time,key=lambda x:(x[0],x[1]))
heap.append(Time[0][1])
for i in range(1,N):
    if Time[i][0] < heap[0]:
        heap.append(Time[i][1])
    else:
        heap.pop(0)
        heap.append(Time[i][1])
print(len(heap))
'''

백준 15903번 카드 합체 놀이

import sys
n,m = map(int,sys.stdin.readline().split())
first = list(map(int,sys.stdin.readline().split()))
for i in range(m):
    first.sort()
    temp = first[0]+first[1]
    first[0] = temp
    first[1] = temp
print(sum(first))