그리디 알고리즘

그리디 알고리즘

: 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

(사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형)

ex) 거스름돈 문제 (큰 단위 동전부터 거슬러야 )

* 가장 큰 순서대로, 가장 작은 순서대로 

 

#큰 수의 법칙

n,m,k=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
result=(lst[-1]*(m//k)*k)+(lst[-2]*(m%k))
print(result)

 

#숫자 카드 게임

n,m=map(int,input().split())
lst=[]
result=[]
for i in range(n):
    lst.append(list(map(int,input().split())))
for j in lst:
    result.append(min(j))
print(max(result))

 

#1이 될 때까지

n,m=map(int,input().split())
cnt=0
while n!=1:
    if n%m!=0:
        n=n-1
    else:
        n=n/m
    cnt+=1
print(cnt)