240311 - 그리디

[robert-min]

문제

1. boj1026 - 보물 링크
2. boj1541 - 잃어버린 괄호 링크
3. boj2847 - 게임을 만든 동준이 링크
4. boj15903 - 카드 합체 놀이 링크
5. boj2457 - 공주님의 정원 링크

[robert-min]

boj1026 - 보물

"""
Return : S의 최솟값
- A는 재배열 가능, B는 불가
- B가 큰 수일 때, A가 작은 수일 경우 최소

B정렬, A 정렬하면 최솟값?
- 위 방법 불가 시 그리디로
"""
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort(reverse=True)
b.sort()

answer = 0
for i in range(len(a)):
    answer += a[i] * b[i]

print(answer)

[robert-min]

boj1541 - 잃어버린 괄호

"""
Return : 값을 최소로

- 마이너스가 나오기 전까지 모든 수를 더해주고, 마이너스가 나오는 순간 그 뒤에 있는 모든 수를 빼두면 됨
"""
input_word = input().split('-')

answer = 0
for i in input_word[0].split('+'):
    answer += int(i)

for i in input_word[1:]:
    for j in i.split('+'):
        answer -= int(j)

print(answer)

[robert-min]

boj2847 - 게임을 만든 동준이

"""
Return : 점수를 몇번 감소하면 되는지
- 오르막 수 인지 확인(무조건 이전 보다 작아야 함)
- 점수를 최소한으로 감소하도록

- 이전 수와 다음수를 비교해서 작으면 이전 수를 감소 cnt += 1
"""
import sys
input = sys.stdin.readline

N = int(input())
nums = []
for _ in range(N):
    nums.append(int(input()))

behind = nums[-1]
cnt = 0
for n in reversed(nums[:-1]):
    if n >= behind:
        while n >= behind:
            n -= 1
            cnt += 1
    behind = n
print(cnt)

[robert-min]

boj15903 - 카드 합체 놀이

"""
Return : 만들 수 있는 가장 작은 점수
m 번 합체 한 후 n 장의 카드에 쓰여 있는 모든 수

- 전체 카드 중 가장 작은 수를 합체(heapq 활용)
"""
import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split())
Q = list(map(int, input().split()))

heapq.heapify(Q)

for _ in range(M):
    x = heapq.heappop(Q)
    y = heapq.heappop(Q)
    temp = x + y
    for _ in range(2):
        heapq.heappush(Q, temp)

print(sum(Q))