09/25 알고리즘

Greedy : 탐욕스러운 , 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘.
그리디는 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순대로'와 같은 기준을 제시해준다.

문제1) 거스름돈
: 거스름돈으로 500,100,50,10원짜리가 있다.. 손님에게 거슬러줘야할 돈이 N원일때 거슬러 줘야할 동전의 최소개수를 구해라. -> 여기서도 "최소개수"가 있다. -> "가장 큰 화폐"부터 돈을 거슬러주는게 가장 적은 갯수로 할 수 있을것이다.

200원을 거슬러줘야한다고 고려해보자. -> 500원은 200원보다 많네? 그러면 넘어가 -> 100원짜리는 어? 2개만 주면 되네 2개! -> 최종 2개

220원을 줘야한다고 고려해보자 -> 위에서 100원짜리 2개를 주고나면 -> 이제 20원이 남는다. -> 20원은 50원보다 많으니까 넘어가 -> 이제 남은 20원은 10원짜리 2개로 하면 되지 -> 최종 4개

코드를 짜보자

n = input()
count = 0

moneys = [500, 100, 50, 10]

for money in moneys:
	count = count + (n // money)
    n = n % money

이렇게 하면 화폐의 종류만큼 반복을 수행하게 된다. -> 화폐 종류가 n개이면 시간 복잡도는 O(n)

문제2) 큰 수의 법칙 : 다양한 수로 이루어진 배열이 있을때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙. 그렇지만 반복을 주어진 K번을 초과해서 할 수는 없음.

3,4,5,4,6으로 이루어진 배열이 있을때 M이 6이고 K가 3이라고 생각하면 6번을 더하고 3번까지만 더할수 있으므로
6+6+6+5+6+6 = 35 . 생각해보니 이건
"가장 큰수를 더할수있는만큼 더하고 그다음으로 큰거 딱 1번더하고 다시 가장 큰수를 더할수있는 만큼하면 될거같다는 느낌이 왔다."
서로 다른 인덱스에 있는 수가 같은 경우에도 서로 다른 것으로 간주한다.

조건
첫째줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며, 자연수는 공백으로 구분.
둘째줄에는 N개의 자연수, K <= M

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

datas = list(map(int,input().split()))
datas.sort() # 입력받은 수를 정렬
first = data[n-1] # 제일 큰수
second = data[n-2] #그 다음 큰수

result = 0
while True:
	for i in range(k):
    	if m == 0:
        	break
        result = result + frist
        m = m - 1
    if m ==0:
    	break
    result = result + second
    m = m -1
    

여기서 반복되는 수열의 길이는 M을 K+1로 나눈몫이 된다. 왜 K가 아니고 K+1이냐? 그건 K는 제일큰거 반복하는 수고 1은 그다음 큰거 이렇게 하나이기떄문에 K+1이다.
1등 1등 1등 1등 2등 : 이런 기분?

그럼 제일 큰거는 몇번 반복될까? int(M // (K+1)) * K + M % (K + 1)

#3 1이 될때까지
: 어떠한 수 N이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두 번째 연산은 N이 K로 나누어떨어질때만 선택할 수 있다.

1. N = N -1 N에서 1을 뺀다.
2. N = N / k N을 K로 나눈다. 나뉘어야지만 가능함

N=17, K=4라고 가정해보자.
N=17 -> (N-1) -> 16 -> /4 -> 4 -> /4 -> 1 == 3번

이걸 풀려면 "최대한 많이 나눠서" 값을 낮추는게 좋을 거같다.

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

while n >= k:
	while n % k != 0:
    	n = n - 1
        result = result + 1
    n = n // k
    result = result + 1
# n이 k보다 작아지면 이제 못나누고 빼줘야하기때문에 빼준다.
while n > 1:
	n = n - 1
    result = result + 1