[백준] 1026, 11399, 2457 (파이썬)

저번 업로드에 이어서 그리디에 관한 내용을 다루었다. 2457번 문제의 경우에는 다른 두 문제에 비해서 난이도가 있는 골드 문제여서 조금 막혔지만, 노트에 차근차근 적어가면서 생각하다보니 확실하게 이해할 수 있었다. 그리디 알고리즘은 계속 경험해야한다는 것을 뼈저리게 느끼고 있다. 앞으로도 꾸준히 풀어나가야겠다.

백준 1026번 보물

import sys
N = int(sys.stdin.readline())
A = list(map(int,(sys.stdin.readline().split())))
B = list(map(int,(sys.stdin.readline().split())))
count = 0
for i in range(N):
    count += min(A) * max(B)
    A.pop(A.index(min(A)))
    B.pop(B.index(max(B)))
print(count)

백준 11399번 ATM

import sys
N = int(sys.stdin.readline())
P = list(map(int,(sys.stdin.readline().split())))
P.sort()
for i in range(1,N):
    P[i] += P[i-1]
print(sum(P))

백준 2457번 공주님의 정원

'''
이런 방식은 조건이 만족하지 않는 경우 0이 출력 안됨
import sys
N = int(sys.stdin.readline())
flower = list()
for i in range(N):
    flower.append(list(map(int,(sys.stdin.readline().split()))))
flower = sorted(flower, key=lambda x: x[3])
flower = sorted(flower, key=lambda x: x[2])
m_locate=0
d_locate=0
count=0
for i,j,k,l in flower:
    if i>m_locate or (i>=m_locate and j>d_locate):
        count+=1
        m_locate = k
        d_locate = l
print(count)
'''
import sys
N = int(sys.stdin.readline())
flower = list()
# 100을 곱해 날짜 형식으로 바꿈 (확실히 이 방식이 편하다)
for _ in range(N):
    date = list(map(int, sys.stdin.readline().split()))
    flower.append([date[0] * 100 + date[1], date[2] * 100 + date[3]])
# 오름차순으로 정렬
flower.sort(key=lambda x:(x[0], x[1]))
count = 0
# 꽃이 지는 날짜 저장
end = 0
# 마지막 꽃의 지는 날
target = 301
while flower:
    # 꽃이 지는 날이 12월1일보다 클 경우, 3월 1일 이후에 꽃이 필 경우 break
    if target >= 1201 or target < flower[0][0]:
        break
    for _ in range(len(flower)):
        if target >= flower[0][0]:
            if end <= flower[0][1]:
                end = flower[0][1]
            #확인한 날짜는 없앰
            flower.remove(flower[0])
        # 꽃의 지는 날이 제일 빨리 피는 꽃보다 작으면 break
        else:
            break
    target = end
    count += 1
if target < 1201:
    print(0)
else:
    print(count)