♻️Greedy - 큰 수의 법칙

dev_itzel_02✨·2024년 11월 12일

♻️Algorithm

목록 보기

3/12

🏷️큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징❗

🔹입력 조건

첫째 줄에 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어지며 각 자연수는 공백으로 분리한다.
둘째 줄에 N개의 자연수가 주어진다.
각 자연수는 공백으로 구분하며, 1 이상 10,000 이하의 수로 주어진다.
입력으로 주어지는 K는 항상 M보다 작거나 같다.

🔹 출력 조건

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

🔹입력 예시

5 8 3
2 4 5 4 6

🔹출력 예시

🧐접근 방안

1) 리스트를 오름차순으로 정렬
2) 가장 큰 수를 K번 더하기
3) 두 번째로 큰 수를 한 번 더하기
4) 총 M번 더할 때까지 2, 3번 반복

📑나의 답안

n, m, k = map(int, input().split())
data = list(map(int, input().split())) # 리스트로 저장
sum = 0
count = 0

# 리스트 정렬
data.sort()

while True:
    # k번 가장 큰 수 더하기
    for _ in range(k):
        if m <= 0:
            break
        sum += data[-1]
        m -= 1
        
    # 두 번째로 큰 수 한 번 더하기
    if m <= 0:
        break
    sum += data[-2]
    m -= 1

print(sum)

📑예제 답안 1

단순하게 푸는 방법

# n, m, k를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
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: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 1씩 빼기
    if m == 0:
        break
    result += second
    m -= 1

print(result)

👉🏼 이 문제는 M이 10,000 이하이므로 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다.

📑예제 답안 2

# n, m, k를 공백으로 구분해 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분해 입력받기
data = list(map(int, input().split()))

# 리스트 정렬(라이브러리 사용)
data.sort()
first = data[-1] # 가장 큰 수
second = data[-2] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m // (k+1)) * k
count += m % (k+1)

result = 0 
result += count * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기

print(result)