[이코테] part2 그리디 - 큰 수의 법칙

오랜만에 블로그 글을 쓴다.

통계를 보니 생각보다 많은 사람들이 방문해서 놀라웠다.

다시 블로그를 활성화시켜보자~ 기록하자 .

---

 

문제

• 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
• 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징
• [2, 4, 5, 4, 6], M=8, K=3
  ⇒ 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46
• 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주
• [3, 4, 3, 4, 3], M=7, K=2
  ⇒ 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28

입력 조건

• 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분된다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분된다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력 예시

5 8 3
2 4 5 4 6

출력 예시

46

 

---

문제풀이

# 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙이다. 
# 하지만 하나의 배열의 원소가 연속해서 K번을 초과하여 더해질 수 없다.

# 문제 풀이 : 제일 큰 값 K 번 + 그 다음 큰 값 1번 + 제일 큰 값 K 번 + 그 다음 큰 값 1번 ...

# n,m,k 공백구분하여 한줄로 입력받기 
n,m,k = map(int, input().split())
# 
array = list(map(int, input().split()))

# array  정렬하기. 가장 큰 수를 먼저 선택할 수 있도록
array.sort()
first = array[n-1]
second = array[n-2]

ans = 0

while True:
    for _ in range(k):
        if m == 0:
            break
        ans += first
        m -= 1
    if m == 0:
        break

    ans += second
    m -= 1

print(ans)

여기서, 수가 들어가는 상황을 공식화한다. 

큰 수가 최대로 들어가야 하니까,

제일 큰 수를 k번 까지 더하고 k+1번에는 두번째 큰 수가 들어간다.

그 다음 다시 제일 큰 수를 k번 더하고 반복이다. 

 

따라서, 그것을 수열이라고 하자 k+1 길이의 수열.

 

- 수열의 길이 K+1- 수열이 반복되는 횟수 M / (K+1)-  가장 큰 수가 더해지는 횟수 int (M/(K+1)) + M % (K+1)(몫으로 나눠지지 않는 상황도 고려하기 때문에 두 항으로 이뤄진다)

# 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙이다. 
# 하지만 하나의 배열의 원소가 연속해서 K번을 초과하여 더해질 수 없다.

# 문제 풀이 : 제일 큰 값 K 번 + 그 다음 큰 값 1번 + 제일 큰 값 K 번 + 그 다음 큰 값 1번 ...


# 반복되는 수열 파악 
# K+1 길이 만큼의 수열이 반복된다.
# 그게 m으로 나뉘면, 총 수열의 길이가 m/k+1
# 가장 큰 수가 더해지는 횟수는 : m/k+1 곱하기 k (수열안에서 가장 큰 수가 k번 등장하니까)
# 근데, m으로 나뉘지 않은 경우는 : m/k+1 * k + m % k+1 (m을 k+1로 나눈 나머지만큼 등장하니까)


# n,m,k 공백구분하여 한줄로 입력받기 
n,m,k = map(int, input().split())
# 
array = list(map(int, input().split()))

# array  정렬하기. 가장 큰 수를 먼저 선택할 수 있도록
array.sort()
first = array[n-1]
second = array[n-2]

# ans = 0

# while True:
#     for _ in range(k):
#         if m == 0:
#             break
#         ans += first
#         m -= 1
#     if m == 0:
#         break

#     ans += second
#     m -= 1
# print(ans)

result = 0

count = int(m/(k+1))*k 
count += m%(k+1)

result += first * count
result += (m-count) * second

print(result)