[2022 하계 모각코] 팀 "한 명 어디갔노" 2회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
2회차: 7/2 19:00 ~ 22:00
목표 : 백준 그리디 알고리즘 관련 3 - 4 문제 풀기

1. 백준 11047번

큰 단위 동전이 작은 단위 동전의 배수관계가 성립한다는 점이 이 문제의 핵심이다. 이 조건으로 인해 그리디 알고리즘이 성립한다. 따라서 K원을 가장 큰 단위 동전에서 작은 단위 순서로 줄이면서 동전의 개수를 구한다.

n, k = map(int, input().split())

money_list = list()

for i in range(n):
    money_list.append(int(input()))

count = 0

money_list.reverse()

for i in money_list:
    count +=  k // i
    k = k % i

print(count)

결과

2. 백준 1946번
   
   서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는자만 선발한다는 원칙을 다음과 같이 해석했다.

• 서류심사 성적으로 먼저 오름차순 정렬을 한다
• 서류심사 1위인 지원자의 면접성적을 기준으로 하위 지원자들의 면접성적을 비교한다
• 면접성적이 더 뛰어난 경우 신입사원 수와 면접성적을 갱신하고 하위 지원자들의 면접성적을 계속 비교한다.

이를 코드로 나타내면 아래와 같다.

import sys

test = int(sys.stdin.readline())

for i in range(test):
    n = int(sys.stdin.readline())
    vt_list = list()
    for j in range(n):
        paper, meet = map(int, sys.stdin.readline().split())
        vt_list.append([paper, meet])

    vt_list_sortp = sorted(vt_list, key = lambda x : x[0])
    cnt = 1
    meet_score = vt_list_sortp[0][1]
    for j in range(1, n):
        if vt_list_sortp[j][1] < meet_score:
            meet_score = vt_list_sortp[j][1]
            cnt += 1

    print(cnt)

결과

3. 백준 1715번

문제 자체는 매우 단순하다. 그냥 오름차순으로 정렬하여 그 값을 계속 더하는 방식이다. 하지만 이를 곧이 곧대로 코드를 구현할 경우 시간초과가 발생했다. 이를 방지하기 위해 sys.stdin.readline() 과 heapq 자료구조를 이용한다.

import sys
import heapq

n = int(sys.stdin.readline())

card_list = []

for _ in range(n):
    heapq.heappush(card_list, int(sys.stdin.readline()))

if len(card_list) == 1:         #카드리스트가 한 개인 경우
    print(0)
else:
    result = 0
    while len(card_list) > 1:
        temp_sum = heapq.heappop(card_list) + heapq.heappop(card_list)
        result += temp_sum
        heapq.heappush(card_list, temp_sum)
    print(result)

결과

4. 백준 1202번
   
   각 가방에 담을 수 있는 최대 가치의 보석을 담는다. 이 때 용량이 작은 가방 먼저 보석을 담아야한다. 각 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 찾을 때 최대힙을 이용한다. 파이썬에서는 최대힙이 구현되어 있지 않으므로 -로 부호를 전환하여 이용한다.

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())
jew = []
for _ in range(n):
    heapq.heappush(jew, list(map(int, sys.stdin.readline().split())))
bags = []
for _ in range(k):
    bags.append(int(sys.stdin.readline()))
bags.sort()

result = 0
temp_jew = []
for bag in bags:
    while jew and bag >= jew[0][0]:
        heapq.heappush(temp_jew, -heapq.heappop(jew)[1])
    if temp_jew:
        result -= heapq.heappop(temp_jew)
    elif not jew:
        break

print(result)

결과