<PART 2> 그리디 예제

 < 2 > 큰 수의 법칙 

n,m,k가 있습니다. n은 배열의 원소 갯수, m은 더하는 횟수, k는 연속한 수가 k번 초과할 수 없음을 의미합니다.
이를 가지고 원소들을 더해서 가장 큰수를 만드는 것이 목적입니다.

ex) n=5이면 2,4,5,4,6로 원소 5개를 주고 m=8, k=3이라면 6+6+6+5+6+6+6+5 =46이 됩니다.

입력예시
5 8 6
2 4 5 4 6

출력 예시
 46

N, M, K = map(int,input().split())
a = sorted(list(map(int,input().split())))
cnt = 0
a_sum = 0
for i in range(M):
    if cnt == K: #k초과지만 cnt가 k가 되면 이미 k수만큼 넣은거라 ==해야함.
        a_sum += a[-2]
        cnt = 0
    else :
        a_sum += a[-1]
        cnt += 1
print(a_sum)

 < 3 > 숫자 카드 게임

처음에 원하는 n x m 형태의 행렬로 선언합니다.
그리고 한가지의 행을 선택하여 가장 낮은 수를 뽑되 최종적으로 그 수가 가장 높은 숫자여야 합니다.

ex) 예시에서 보는 것과 같이 1행의 최소는 1, 2행은 1, 3행은 2입니다. 그러므로 3행을 뽑고 최솟값을 출력시키는 것이 목적입니다.

입력예시
3 3
3 1 2
4 1 4
2 2 2

출력예시
2

n,m = list(map(int,input().split()))
 
result= 0
for i in range(n):
    data = list(map(int,input().split()))
    min_data = min(data) #최솟값을 구하고
    result=max(result,min_data) #최솟값구한것들중에 큰값
print(result)

n,k = list(map(int,input().split()))
count = 0
 
while True:
    #n이 m으로 나눠떨어질 수 있도록 -1을 진행
    div_num = (n//k) * k
    count += n-div_num
    n = div_num
    # 더이상 나눠줄 수 없을 때 탈출
    if n < k:
        break
    #나눗셈 진행
    n = n//k
    count += 1
 
#마지막 수에서 -1한 값이 1을 빼주는 횟수자체가 됨.
count += n-1
print(count)

풀이: -1을 하는 것보다 나눗셈을 진행하는 것이 무조건 최소횟수로 가는 방법입니다. 그렇기 때문에 나눗셈이 진행될 수 있도록 처음에 -1을 진행 그런 다음 나눠줍니다. 이게 기본과정입니다.

여기서 나눠지게 만들기 위해 -1을 한 횟수를 적을 때 COUNT도 같이 적어줍니다.
여기서 처음부터 4 5로 주어지면 나눠지지가 않으므로 If문을 걸어 나눠지는지 확인합니다. 나눠진다면 나눗셈을 하고 20 4 케이스처럼 한번더 위의 과정을 진행합니다.

결국엔 n<k인 순간이 오게되고 이 때는 구한 값에서 1을 뺀 값이 -1을 해야되는 횟수와 같습니다.