[알고리즘] #02 그리디 알고리즘-큰 수의 법칙 문제

🛠 큰 수의 법칙 문제

🔧  문제 

 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙을 큰 수의 법칙이라고 하자. 

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

(인덱스가 다르면 다른 수라고 가정한다.)

 

✅ 입력 조건

1. 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= L <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000 이하의 수로 주어진다.

3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

✅ 출력 조건

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

 

✅ 입력 예시	✅ 출력 예시
5 8 3 2 4 5 4 6	46

 

---

🔧 아이디어

1) 입력값

- 우선 N개의 크기를 가지는 배열을 생성하고, 둘째줄에 입력받은 자연수들을 저장한다.

 

- 수가 같아도 인덱스가 다르면 다른 수로 여기기 때문에, 둘째줄에 입력받는 수들 중 가장 큰 수가 중복되어 있는 경우

K값에 상관없이 최대값 * M 을 통해 결과를 얻을 수 있다. (아래의 예 참고 - 6+6+6+6+6+6+6+6)

✅ 입력 예시	✅ 출력 예시
5 8 3 2 4 5 6 6	48

 

- 최대값이 도출되기 위해서는 둘째줄에 입력받는 수들 중 (최대값 * K) + 그다음 최대값 + (최대값 * M-k-1)을 계산해야 한다.

✅ 입력 예시	✅ 출력 예시
5 8 3 2 4 5 4 6	46

이 상황을 예로 들어보자면 N = 5 / M = 8 / K = 3이다. 

즉, N개의 숫자가 둘째줄에 입력되고 한 인덱스에 해당하는 수는 연속으로 최대 3번까지 더해질 수 있으며 총 8번의 덧셈을 해야 한다.

 

결과로 최대값을 내야 하므로 최대값을 최대한 많이 더해야 한다.

(6+6+6)=> 총 5번의 덧셈이 남았고 한 인덱스에 해당하는 수는 연속으로 3번까지 더해질 수 있으니 그 다음으로 큰 수인 5를 한 번 더해준다.

(6+6+6)+5 => 총 4번의 덧셈이 남았고 중간에 5를 한번 더했기 때문에 이제 다시 최대값인 6을 더할 수 있게 되었다. 

(6+6+6)+5+(6+6+6) => 총 1번의 덧셈이 남았고 6을 3번 더했기 때문에 이제 5를 더해 연속을 끊어야 한다.

(6+6+6)+5+(6+6+6)+5 => 총 0번의 덧셈이 남아 결과값으로 46을 출력한다.

 

좀 더 간단하게 공식화 해보자. 위의 예를 보면 (6+6+6)+5 가 반복되는 것을 볼 수 있다.

M = 8일 때, 최대값인 6이 얼만큼 더해지는지를 알아보자. 

반복되는 (6+6+6)+5를 하나의 덩어리라고 생각하면 8 안에는 2개가 들어갈 수 있다. 한 덩어리 안에 6이 3개씩 들어있으니 

최대값인 6은 총 6번 더해진다. 식으로 나타내면 M // (K+1) * K번 더해진다.

 

만약 M = 9라면? 2개의 덩어리가 들어가고도 1이 남는다.

이 상황은 초등학생때 배운 연산인 '나머지 연산'을 활용할 수 있다.

9 / 4 = 몫이 2이고 나머지가 1이다. 나머지는 절대 4이상일 수 없다.

따라서 아래와 같이 나머지가 어떤 수가 나오든 덩어리가 2번 반복된 후이므로 최대값인 6이 더해질 수있는 상황이 된다.

[(6+6+6)+5] + [(6+6+6)+5] + ?

 

따라서 일반화시키면, 
{M // (K+1) * K} + {M % (K+1)}가 된다.

 

그럼 두번째로 큰 값인 5는 얼만큼 더해지는지 알아보자.

M = 8일때, 2번

M = 9일때, 2번

M = 10일때, 2번

M = 11일때, 2번

M = 12일때, 3번

따라서 일반화시키면 M // (K+1)이 된다.

 

이를 활용해서 코드를 작성해보자.

---

🔧 코드 작성

# split으로 분리된 N, M, K가 속한 배열을 map함수를 통해 int로 형변환한 후 각각의 변수에 저장한다.
N, M, K = map(int, input().split())

# list()를 통해 둘째줄에 입력받는 수들을 리스트에 저장한다.
InputArray = list(map(int, input().split()))

# 최대값과 그 다음으로 큰 값을 알아내기 위해 내장함수 .sort()를 이용한다
# 내림차순으로 정렬위해서는 reverse = True 를 넣어주어야 함. 디폴트는 오름차순
InputArray.sort(reverse=True) # .sort()함수는 리턴값이 없음 !!주의!!

result = 0 # 결과로 반환할 변수생성

if(InputArray[0] == InputArray[1]): # 만약 최대값과 그 다음 큰 값이 같다면
    result = InputArray[0] * M
else:
    max_count = int(M / (K+1)) * K + M % (K+1) # 최대값이 더해질 횟수
    second_count = int(M / (K+1)) # 두번째 큰 값이 더해질 횟수
    result = max_count * InputArray[0] + second_count * InputArray[1]

print(result)