[Algorithm] 백준 11047번, 1931번 Python

0. 그리디 알고리즘

Greedy Algorithm

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아보인느 것을 선택, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 방법
  
  

1. 백준 11047번 - 동전 0

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

문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N, K 주어짐
둘째 줄부터 N+1번째 줄까지 동전의 가치가 오름차순으로 주어짐

출력
K원을 만드는 데 필요한 동전 개수의 최솟값

접근 방식
1. 동전 목록을 내림차순(가치가 큰 것부터)으로 정렬
2. 첫번째 동전부터 순서대로 K 값을 넘기기 전까지 값을 보탬
3. 값이 K가 되면 종료하고 몇 개의 동전이 사용되었는지 출력

import sys

input = sys.stdin.readline

N, K = map(int, input().split())

coins = []

coins = [int(input()) for _ in range(N)]
coins.reverse()

개인적으로 sys 모듈은 시간을 조금이라도 줄이기 위해 항상 사용한다.

sys 모듈은 파이썬 인터프리터가 제공하는 변수와 함수를 직접 제어할 수 있게 해주는 모듈이다. https://wikidocs.net/33

N값과 K값을 받고, N개의 동전의 가치를 받기 위해 for문을 실행한다.

그런 다음 reverse()를 이용하여 내림차순으로 동전 목록을 정렬한다.
coins.reverse() 말고 coins.sort(reverse=True) 사용해도 된다.
위 문제에서는 애초에 동전의 가치가 오름차순으로 제공된다고 하였기 때문에 단순히 목록을 뒤집어주기만 해도 내림차순으로 바뀌기 때문에 reverse()를 사용한 것이다.

내림차순으로 정렬한 후에는 본격적으로 계산을 진행한다.
조건은 2가지이다.

1) 해당 동전의 가치가 K보다 작아야 한다.
예를 들어, 35000원을 만들어야 하는 경우에 50000원짜리 동전을 사용할 수 없다.
2) 사용한 동전의 총합이 K보다 작거나 같아야 한다.
너무 당연한 조건이다. 이때 사용한 동전의 총합을 계산하는 대신 동전을 사용했을 때 K에서 해당 동전의 가치만큼 빼고, 이 과정을 K가 0이 될 때까지 반복할 것이다.

count = 0
for coin in coins:
    if coin <= K and K % coin >= 0:
        num = K // coin
        K -= num * coin
        count += num
    if K == 0:
        print(count)
        break

while문을 사용하면 시간초과가 발생한다. 그래서 동전의 가치를 하나하나 빼는 대신, 총 얼마를 뺄 수 있는지 계산하고(K // coin) 한 번에 빼는 방식을 사용하였다.

최종 코드

import sys

input = sys.stdin.readline

N, K = map(int, input().split())

coins = []

coins = [int(input()) for _ in range(N)]
coins.reverse()

count = 0

for coin in coins:
    if coin <= K and K % coin >= 0:
        num = K // coin
        K -= num * coin
        count += num
    if K == 0:
        print(count)
        break

2. 백준 1931번 - 회의실 배정

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

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력
첫째 줄에 회의 수(N) 주어짐
둘째 줄부터 N+1번째 줄까지 회의 시작시간과 끝나는 시간 주어짐

출력
최대 사용할 수 있는 회의의 최대 개수 출력

접근 방식
1. 시작시간이 이른 순으로 정렬한다.
2. 다시 끝나는 시간이 이른 순으로 정렬한다.

import sys

input = sys.stdin.readline

N = int(input())
list = []

for i in range(N):
    start, end = map(int, input().split())
    list.append([start, end])

list = sorted(list, key=lambda l: l[0])
list = sorted(list, key=lambda l: l[1])

endTime = list[0][1]
cnt = 1

for i in range(1, N):
    if list[i][0] >= endTime:
        endTime = list[i][1]
        cnt += 1

print(cnt)

시작시간이 이른 순으로 정렬해야 한다는 것은 누구나 떠올릴 수 있다. 다음으로 끝나는 시간이 이른 순으로 정렬해야 하는데, 일찍 회의가 끝날수록 남은 시간동안 더 많은 회의를 할 수 있기 때문이다.

list = sorted(list, key=lambda l: l[0])
list = sorted(list, key=lambda l: l[1])

이와 같이 정렬을 두 번 진행해도 되고,

list = sorted(list, key=lambda l: (l[1], l[0]))

이와 같이 한 번에 진행해도 된다.

(+) list.sort(~)나 list = sorted(list, ~)나 동일하게 작용한다.