[그리디 알고리즘] ★ 큰 수의 법칙

큰 수의 법칙

1) 문제 해결 아이디어

입력받은 리스트를 내림차순 정렬한다.

사실상 해당 리스트에서 필요한 값은 가장 큰 값, 2번째로 큰 값 2개이다.

가장 큰 값을 연속 K번 더하고 2번째로 큰 값을 한번 더하는 연산을 반복하면 된다.

 

2) 소스코드

(풀이1) 정석적인 방식

# 더할 횟수, 연속 덧셈 횟수
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
res = 0

data.sort(reverse=True)  # 내림차순 정렬
first = data[0]  # 가장 큰 수
second = data[1] # 두번째 큰 수

while True:
  # first 연속 k번 더하기
  for i in range(k):
    # 탈출 조건(더할 횟수가 남지 않았으면)
    if(m == 0):  
      break
    #print(first, end=" ")
    res += first
    m -= 1    # 더할 횟수 차감
  if(m == 0):
    break
  # second 1번 더하기
  res += second
  m -= 1      # 더할 횟수 차감
  #print(second, end=" ")
print(res)

(풀이2) 수학적 접근

# 더할 횟수, 연속 덧셈 횟수
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
res = 0

data.sort(reverse=True)  # 내림차순 정렬
first = data[0]  # 가장 큰 수
second = data[1] # 두번째 큰 수

sCount = m // (k + 1)    # second 더할 횟수
fCount = m - sCount      # first 더할 횟수

res = first * fCount + second * sCount
print(res)

가장 큰 값을 연속 K번 더하고 2번째로 큰 값을 한번 더하는 연산을 반복된다는 점에 주목하여

총 더할 횟수(m)에서 가장 큰 값과 2번째로 큰 값을 각각 몇번 더해야하는지 구하여 계산한다.

 

(k번 연속 더하고 1번 더하기) 연산을 한 세트로 생각하면

총 더할 횟수(m)을 (k+1)로 나눈 몫이 2번째로 큰 값을 한 번 더하는 연산을 몇 번 해야할지이다.

가장 큰 값을 K번 연속 더하는 연산은 총 더할 횟수(m)에서 이전에 구한 값을 뺀 값이다.

 

여기서 k가 아닌 (K+1)인 이유는?

[first * K + second] 를 한 연산으로 보기로 했기 때문에