[Python] 큰 수의 법칙(그리디)

문제 

• 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수 만들기
• 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 k번을 초과하여 더해질 수 없다
• 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주

입력

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

출력

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

문제 풀이 1

• 문제에서 필요한 값은 첫 번째로 큰 수와 두 번째로 큰 수이다
• m의 값이 0이 될 때 까지 첫 번째로 큰 수를 K번 더한 후 두 번째로 큰 수를 한 번 더한다
• while문과 for문 안에서 m의 값이 0이 되는 경우를 고려하여 break도 작성
• 연산 결과를 출력한다

코드

n, m, k = map(int,input().split())
data = list(map(int,input().split()))
data.sort(reverse=True)
first = data[0]
second = data[1]

result = 0
# m이 될 때 까지 k번씩 계속 더하기
while m > 0 :
    for i in range(k):
        result += first
        m -= 1
        if m < 0:
            break

    if m < 0:
        break
    result += second
    m -= 1
    b 
print(result)

문제풀이 2

• 반복되는 수열의 길이는 K + 1 (큰 수 K만큼 더한 후, 두 번째로 큰 수를 한 번 더하기 때문)
• 이 때  M // 수열의 길이는 반복되는 수열의 횟수
• 반복되는 수열의 횟수 * K 는 가장 큰 수의 횟수
• M이 (K + 1)로 나누어 떨어지지 않는다면 나머지의 크기만큼 가장 큰 수의 횟수를 더해준다
• 마지막으로 전체 연산의 횟수 M에서 가장 큰수의 횟수를 빼면 두 번째로 큰 수의 횟수
• 변수에 가장 큰 수와 두 번째로 큰수를 더한 후 값을 출력

코드

# 배열의 길이, 연산 횟수, 연속될 수 있는 경우
n, m, k = map(int,input().split())
data = list(map(int,input().split()))
data.sort()
first = data[n - 1]
second = data[n - 2]

# 가장 큰 수의 개수
count = int(m // (k + 1)) * k
count += m % (k + 1)

result = count * first
# 두 번째로 큰 수의 횟수는 전체연산횟수 - 가장 큰 수의 횟수
result += (m - count) * second
print(result)