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)