[Algorithm] D-4 그리디 백준 문제

1. 11399번 ATM

코드

n=int(input())
data=list(map(int,input().split()))

data.sort()
result=0

for i in range (n):
    result+=data[i]*(n-i)

print(result)

과정

P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분

-> 1번 사람 3분
2번 사람 3분 + 1분
3번 사람 3분 + 1분 + 4
4번 사람 3+1+4+3
5번 사람 3+1+4+3+2

=

3분 (인원수) + 1분 (인원수-1) +4분 * (인원수-2) + 3분 (인원수 - 3) + 2분 (인원수 -4)

11047.py 동전 0

코드

n,k=map(int,input().split())
data=[]
count=0
for i in range (n):
    data.append(int(input()))
for i in range(n-1,-1,-1):
    if k==0:
        break
    if data[i]>k:
        continue
    count+=k//data[i]
    k=k%data[i]
print(count)

과정

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

1000원 4개 100원 2개

거꾸로 탐색 해서 몫과 나머지 구함

2839 설탕 배달.py

코드

n=int(input())
count=0


while n>=0:
    if n%5==0:
        count+=n//5
        print(count)
        break
    n-=3
    count+=1
else:
    print(-1)

과정

봉지는 3킬로그램 봉지와 5킬로그램 봉지
1. 5로 나누어 떨어지는 수를 만들기위해(그리디하다) 3을 빼준다. 5로 나누어 떨어지면 5로 나눠준다.
2. 5로 안 떨어지는경우