EDOC 2023-2 7주차 과제

06-1 그리디 알고리즘

 

032. 동전 0 (백준 11047번)

 

https://www.acmicpc.net/problem/11047

 

from sys import stdin

n, k = map(int, stdin.readline().split())
coin = [int(stdin.readline()) for _ in range(n)]
ans = 0

for i in range(n-1, -1, -1):
    ans += k // coin[i]
    k = k % coin[i]

print(ans)

 

그리디 알고리즘의 문제들의 특징은 이 문제가 그리디 알고리즘을 이용해서 풀어야 한다는 것을 아는 상태에서는 매우 쉽지만, 그리디라는 아이디어 떠올리는 것 자체가 매우 어렵다는 것이다. 어려운 문제일수록 그렇다고 한다. 그래서 그리디 알고리즘을 학습할 때는 이 문제를 그리디로 풀어도 되는 이유가 무엇인지, 매 순간마다 가장 효율적인 선택을 했을 때 전체적으로 봤을 때도 그것이 가장 효율적인 선택이라는 것을 보장하는 조건이 무엇인지를 생각하는 것이 도움이 될 것 같다. 예를 들어, 이 문제에서는 "Ai는 Ai-1의 배수"라는 조건이 중요하다. 이 조건이 있기 때문에 그리디로 푸는 것이 가능한 것이다. (정답)

 

---

 

033. 카드 정렬하기 (백준 1715번)

 

https://www.acmicpc.net/problem/1715

 

from sys import stdin
from queue import PriorityQueue

n = int(stdin.readline())
ans = 0
que = PriorityQueue()

for _ in range(n):
    que.put(int(stdin.readline()))

while que.qsize() > 1:
    x1 = que.get()
    x2 = que.get()
    que.put(x1 + x2)
    ans += (x1 + x2)

if n == 1:
    print(0)
else:
    print(ans)

 

(정답)

 

---

 

034. 수 묶기 (백준 1744번)

 

https://www.acmicpc.net/problem/1744

 

from sys import stdin
from queue import PriorityQueue

n = int(stdin.readline())
pos = PriorityQueue()
neg = PriorityQueue()
ans = 0
zero = False

for _ in range(n):
    x = int(stdin.readline())
    if x > 1:
        pos.put(x * (-1))
    elif x < 0:
        neg.put(x)
    elif x == 1:
        ans += 1
    else:
        zero = True

while pos.qsize() > 1:
    ans += (pos.get() * pos.get())
if not pos.empty():
    ans -= pos.get()

while neg.qsize() > 1:
    ans += (neg.get() * neg.get())
if not neg.empty() and not zero:
    ans += neg.get()

print(ans)

 

두 개의 우선순위 큐를 이용하여 푼 풀이. 파이썬에서 우선순위 큐는 가장 작은 값이 먼저 나오는데, 이를 잘 생각해서 부호를 적용시켜주어야 한다. 1은 유일하게 곱해서 더하는 것보다 그냥 더하는 게 더 크기 때문에 개수를 따로 세어주어야 하는 것이고, 0은 1개라도 있는지 없는지만 체크하면 된다. (정답)

 

from sys import stdin

n = int(stdin.readline())
pos = []
neg = []
ans = 0
zero = False

for _ in range(n):
    x = int(stdin.readline())
    if x > 1:
        pos.append(x)
    elif x < 0:
        neg.append(x)
    elif x == 1:
        ans += 1
    else:
        zero = True

pos.sort(reverse=True)
neg.sort()

for i in range(0, len(pos), 2):
    if i + 1 < len(pos):
        ans += (pos[i] * pos[i+1])
    else:
        ans += pos[i]

for i in range(0, len(neg), 2):
    if i + 1 < len(neg):
        ans += (neg[i] * neg[i+1])
    else:
        if not zero:
            ans += neg[i]

print(ans)

 

근데 생각해보니 정렬로도 풀 수 있을 것 같아서 정렬로 다시 풀어봤다. 비슷하지만, pos는 내림차순으로, neg는 오름차순으로 정렬해주었다. 우선순위 큐와는 달리 부호를 바꿔서 넣어야 하고 이런 문제가 없어서 오히려 간단했다. 이렇게 제출했더니 오히려 시간이 줄었다..!!! (정답)

 

 

위가 정렬로 푼 풀이, 아래가 우선순위 큐로 푼 풀이.

 

---

 

035. 회의실 배정 (백준 1931번)

 

https://www.acmicpc.net/problem/1931

 

from sys import stdin

n = int(stdin.readline())
data = []
cnt = 0
end = -1

for _ in range(n):
    s, e = map(int, stdin.readline().split())
    data.append((s, e))

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

for i in range(n):
    if data[i][0] >= end:
        end = data[i][1]
        cnt += 1

print(cnt)

 

교재에서는 이차원 배열에 담아 정렬했지만 나는 튜플에 담아 정렬했다.

이차원 배열, 튜플 모두에 쓸 수 있는 여러 값으로 정렬하는 방법.

 

lst = [[2, 1], [3, 4], [1, 2], [1, 3], [3, 2]]
lst.sort(key=lambda x: (x[0], -x[1]))
print(lst)
# [[1, 3], [1, 2], [2, 1], [3, 4], [3, 2]]

lst = [[2, 1], [3, 4], [1, 2], [1, 3], [3, 2]]
lst.sort(key=lambda x: (x[1], x[0]))
print(lst)
# [[2, 1], [1, 2], [3, 2], [1, 3], [3, 4]]

 

(정답)

 

---

 

036. 잃어버린 괄호 (백준 1541번)

 

https://www.acmicpc.net/problem/1541

 

from sys import stdin

a = list(map(str, stdin.readline().split("-")))

def mySum(a):
    sum = 0
    tmp = list(map(int, a.split("+")))
    for i in tmp:
        sum += int(i)
    return sum

sum = mySum(a[0])

for i in range(1, len(a)):
    sum -= mySum(a[i])

print(sum)

 

(정답)