[python] 단계별로 풀어보기 - 16단계

 

 

 

백준 16단계 그리디 알고리즘

 

 

https://www.acmicpc.net/step/33

그리디 알고리즘 단계

 

 

그리디 알고리즘

최적의 해를 구하는 데에 사용되는 근사적인 방법. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

즉, 다음 것을 생각하지 않고 지금 당장에서 가장 최고의 답을 구하는 것! 따라서 가장 좋은 결과를 얻는 것이 보장되는 것은 아님.

 

 

 

 

---

 

 

 

16-1) 백준 11047번: 동전 0

 

N, K = map(int, input().split())
coin = []
count = 0

for i in range(N):
    a = int(input())
    coin.append(a)

coin.sort(reverse = True)

while K != 0:
    for i in coin:
        count += K//i
        K %= i

print(count)

 

각각을 모두 입력 받은 뒤 받은 코인을 역순으로 정렬한다

최솟값을 구하려면 제일 큰 것 부터 계산해야하기 때문이다.

 

그 후,

K가 0이 될때까지 K에서 i를 나눈 몫을 더하고, 그 나머지를 K에 다시 저장해주는 것을 반복한다

 

 

 

 

 

 

16-2) 백준 1931번: 회의실 배정

 

#회의가 빨리 끝나는 순서대로 정렬해야 함 => 빨리 끝날 수록 뒤에 올 수 있는 회의 수가 많음
#끝나는 시간이 가장 빠른 순으로 정렬. 시작하는 시간의 오름차순으로 정
N = int(input())
meeting = []
for i in range(N):
    meeting.append(list(map(int, input().split())))

#key에 2개의 인자를 두면 인자늬순서대로 정렬. x[1]먼저 정렬하고 x[0] 정렬
meeting = sorted(meeting, key = lambda x: [x[1], x[0]])


#빨리 끝나는 것 중 가장 빨리 시작하는 순서대로 더해준다.
result = 0
start = 0
for meet in meeting:
    if meet[0] >= start:
        start = meet[1]
        result += 1
        
print(result)

 

이 문제는 헷갈려서 계속해서 반복문을 돌리면서 계산했다가 시간초과가 나서 구글링을 한 문제이다.

주석을 자세히 작성했으므로 추가 설명을 생략하겠다.

 

 

 

 

 

 

 

16-3) 백준 11399번: ATM

 

N = int(input())
time = list(map(int, input().split()))

time.sort()
count = []

for i in range(N):
    count.append(time[i] * N)
    N = N-1


print(sum(count))

 

입력받은 시간 Pi를 정렬한 뒤, time * N을 한 값을 리스트에 추가해주고

N을 N-1로 바꿔준다

그 후, 리스트에 추가된 모든 값을 더한 결과를 출력해준다.

 

 

 

 

 

 

 

16-4) 백준 1541번: 잃어버린 괄호

 

#최초로 -가 나오기 전의 모든 수는 더하고, -가 나오면 그 뒤의 모든 수를 빼준다
a = input().split('-')     # '-' 기준으로 쪼개준다
num = []

for i in a:
    cnt = 0
    s = i.split('+')    # '+' 기준으로 쪼개준다    
    for j in s:
        cnt += int(j)    #쪼개준 것을 기준으로 cnt에 그 합을 더해준다
    num.append(cnt)   #num 리스트에 cnt 값들 저장
    
n = num[0]  #제일 처음 수를 기준으로 계산

for i in range(1, len(num)):    
    n -= num[i]  #-가 나오기 전에 더해준 수들 모두 빼준다
    
print(n)

 

기호를 기준으로 split하는 법을 모르고 다른 방법으로 해결을 하다가

너무 답이 나오지 않아서 다른 분들의 코드를 참고했다

그래서 내가 이해한 것을 토대로 주석을 작성했다

 

 

 

 

 

 

 

16-5) 백준 13305번: 주유소

 

N = int(input())
length = list(map(int, input().split()))
price = list(map(int, input().split()))

#처음 출발할때 무조건 기름 필요
result = length[0] * price[0]
good_price = price[0]

for i in range(1, N-1):
    if good_price > price[i]:
        result += price[i] *  length[i]
        good_price = price[i]
        
    else:
        result += good_price *  length[i]


print(result)

 

가장 중요한 것은 출발할 때 기름이 필요하다는 점이었다

그 다음, 제일 처음 값을 최저값이라고 가정하고 선택을 해준다

반복문을 돌면서 만약 정해둔 최저값보다 작은 값이 나오면 그 값으로 계산을 해주고, 최저값을 바꿔준다.

그렇지 않다면 정해둔 최저값으로 계산해준다.

 

그럼 작은 수가 나올때마다 최저값을 바꿔주므로 최소값으로 계산할 수 있다.

 

 

참고로 min함수를 지속적으로 사용하면 시간초과가 난다.