[이코테][Chapter 3][문제] 2. 큰 수의 법칙

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

 

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

 

[출력]
큰 수의 법칙에 따라 더해진 답

 

[예시]

• 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M=8, K=3이라고 가정하자. 특정한 인덱스의 수를 연속해서 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이 된다. (다른 인덱스의 4이기 때문에 계속 4를 더할 수 있다)

---

간단한 수학적 연산이 필요한 그리디 알고리즘이다.

예시에서 풀이 방법이 거이 다 나와있다. 2가지 방법으로 나누어 푼다.

 

1. 가장 큰 수, 2번째로 큰 수가 다를 때

--> 가장 큰 수를 M번만큼 곱한다.

--> 그 후 (가장 큰 수 - 2번째로 큰 수)를 M//K만큼 곱해서 뺀다.

2. 가장 큰 수, 2번째로 큰 수가 같을 때

--> 가장 큰 수를 M번만큼 곱한다.

 

#큰 수의 법칙
#(시작시간 : 2시 10분)

#입력 조건
print("n m k 입력")
n, m, k = map(int, input().split())
print("배열의 데이터 입력")
data = list(map(int, input().split()))

import time
start_time = time.time()

#알고리즘 과정
#규칙적으로 수를 더하므로 "탐욕 알고리즘(Greedy Algorithm)"을 사용할 수 있다.

#문제풀이 과정
#조건 1. 가장 큰 수가 단일로 존재하고, 두번째로 큰 수가 존재할 때
#가장 큰 수를 K번 더한 후, 두번째로 큰 수를 더하는 식으로 반복한다.

#조건 1 식 세우기
#가장 큰 수 = first, 두번째로 큰 수 = second 라고 하자.
#K는 "배수"로 인식하면 문제를 더 쉽게 풀 수 있다.
#그러면 first를 M번 반복하는데, first-second의 값을 K만큼 반복하여 빼준다.
#그러면 식은 first*M - (first-second)*(M//K)

data = sorted(data, reverse=True)
first = data[0]
second = data[1]

if(first != second):
    output = first * m - (first-second) * (m//k)

#조건 2. 가장 큰 수와 두번째로 큰 수가 동일할 때
#그 수를 M번 곱하면 된다.

#조건 2 식 세우기
#first*M
if(first == second):
    output= first * m

end_time = time.time()
print("결과 : ", output)
print("프로그램 실행 시간 : ", end_time - start_time)