[Coding Test] 이코테 - Greedy Algorithm (그리디 알고리즘)

1. Greey Algorithm (그리디 알고리즘)

• 현재 상황에서 당장 좋은 것만 고르는 방법
• 기준에 따라 좋은 것을 선택
  • '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시

• 그리디 알고리즘의 정당성
  • 문제풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출 가능
  • 그리디 알고리즘으로 해결할 수 없을 경우 → 다이나믹 프로그래밍, 그래프 알고리즘

2. 큰 수의 법칙

• N개의 숫자로 이루어진 배열을 사용하여 숫자를 M번 더하여 가장 큰 수 만들기
• 가장 큰 수와 두번째로 큰 수만 저장
• 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복
  • N = 배열의 크기
  • M = 숫자가 더해지는 회수
  • K = 특정한 인덱스에 해당하는 수가 연속해서 k번 초과하여 더해질 수 없음

#단순하게 푸는 답안 예시

N,K,M = map(int,input().split())
data = list(map(int,input().split()))

data.sort() #입력받은 수 정렬하기
first = data[n-1] #가장 큰 수
second = data[n-2] #두 번째로 큰 수

result = 0

while True:
    for i in range(K): #가장 큰 수를 k번 더하기
        if M == 0:
            break
        result += first
        M -=1 #더할 때마다 1씩 빼기

    if M == 0:
        break
    result += second #두 번째로 큰 수를 한번 더하기
    M-=1 #더할 때마다 1빼기

print(result)

 

• 😒 단순 풀이는 효율적 x → 😊 반복되는 수열에 대해서 파악해야 함
  • 반복되는 수열의 길이 = K+1
  • 수열이 반복되는 회수 = M/(K+1)
  • 가장 큰 수가 등장하는 횟수 =int(M/(K+1)) * K + M%(K+1)

#반복되는 수열에 대해서 파악해야 함

N, M, K= map(int,input().split())
num=list(map(int,input().split()))
num.sort()

first, second = num[-1], num[-2]

result=M//(K+1)*(K*first+second)+M%(K+1)*first
print(result)