큰 수의 법칙

📌문제

예제 3-2 큰 수의 법칙

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

 

배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 더할 수 있는 최대 횟수 K

 

📌풀이 1(단순한 방법)

가장 큰 수와 두 번째 큰 수만 저장

가장 큰 수를 K번(연속으로 더할 수 있는 최대 횟수) + 두 번째 큰 수 1번 + ... 반복

 

📌코드 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:  # 더해지는 횟수가 모두 소진되었다면 반복문 탈출
            break
        result += first
        m -= 1  # 더할 때마다 더해지는 횟수 1씩 감소
    if m == 0:
        break
    result += second  # 두 번째로 큰 수 한 번 더하기
    m -= 1

print(result)

 

문제점: M이 10000 이하이므로 이 방식으로 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면 시간 초과 발생할 것

 

📌풀이 2

반복되는 수열에 대해 파악

ex) [2, 4, 5, 4, 6]

가장 큰 수: 6

두 번째로 큰 수: 5

 

M(더해지는 전체 숫자 개수): 8

K(연속해서 더할 수 있는 횟수): 3

 

(6+6+6+5)+(6+6+6+5)=46

{6,6,6,5} 수열이 반복됨을 알 수 있음

 

반복되는 수열의 길이 = K+1

수열이 반복되는 횟수 = M // (K+1)

가장 큰 수가 등장하는 횟수 = (M // (K+1)) * K (각 수열마다 K번씩 등장)

 

수열이 반복되는 횟수가 딱 나누어 떨어지지 않을 경우 나머지만큼 추가적으로 큰 수를 더해줘야 함

+ M % (K+1)

 

'가장 큰 수가 더해지는 횟수' = (M // (K+1)) * K + M % (K+1)

 

📌코드 2

# 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]  # 두 번째로 큰 수(맨 뒤에서 두 번째 인덱스)

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

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

print(result)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬