[CH3 그리디] 큰 수의 법칙

큰 수의 법칙

• 일반적으로 통계 분야에서 다루어지는 내용이지만, 이 책에서는 새로운 방식으로 다르게 사용한다고 한다!
• 동빈이의 큰 수의 법칙 : 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
• 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다!

ex) 배열 {2, 4, 5, 4, 6} 에서 M=8, K=3이면

=> 특정 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로, 6+6+6+5+6+6+6+5=46 이 된다!

 

• 만약 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다

ex) 배열 {3, 4, 3, 4, 3}으로 이루어진 배열이 있을 때 M=7, K=2 이면?

=> 2번쨰 원소와 4번쨰 원소는 4로 값은 같지만 인덱스가 다르기 떄문에 다른 것으로 간주한다!

=> 따라서 4+4+4+4+4+4+4=28 이 된다!

 

---

이제 책의 예시를 풀어보자!

 

[입력 조건]

• 첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다
• 둘쨰 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다
• 입력으로 주어지는 K는 항상 M보다 작거나 같다

[출력 조건]

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

 

입력 예시)

5 8 3

2 4 5 4 6

 

출력 예시)

46

 

---

[문제 풀이]

• 전형적인 그리디 알고리즘 문제
• 이 문제를 해결하려면, 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다
• 연속으로 더할 수 있는 횟수는 최대 K번이므로 가장 큰 수를 K번 더하고 두 번쨰로 큰 수를 한 번 더하는 연산을 반복하면 된다

[코드]

파이썬)

#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
            break
        result += first
        m -= 1
    if m==0: #m이 0이면 바깥 반복문도 탈출
        break
    result += second
    m -= 1

print(result) #결과 출력

저번에 파이썬으로 문자열 문제 풀어봤는데 엄청 쉽게 풀리길래 파이썬도 가능하면 연습해보려고!

 

아래는 결과화면임!

(옹졸)

 

---

위의 방식으로 풀어도 되지만, M의 크기가 커지면 시간 초과가 발생한다고 한다!

그럼 더 간단하게 풀어보자!

 

이 때는 반복되는 수열에 대해 파악해야 한다

만약 가장 큰 수는 6, 두번쨰로 큰 수가 5이고 M=8, K=3이면 결과는 아래와 같다

=> 6+6+6+5+6+6+6+5

 

위의 결과를 보면 (6+6+6+5)가 반복해서 더해지는 수열임을 알 수 있다

그렇다면 반복되는 수열의 길이는? -> 가장 큰 수를 K번 연속해서 더하고 그 뒤에 두번째로 큰 수를 한 번 더하므로 (K+1)이 된다!

따라서 결과는 M을 (K+1)로 나눈 값과 가장 큰 수를 곱해준 값이 된다!

 

이 때 만약 M이 (K+1)로 나눠지지 않으면 가장 큰 수를 추가로 더해줘야 한다

=> 가장 큰 수를 M % (K+1) 번 더해줘야 한다!

 

이를 정리하면 가장 큰 수가 더해지는 횟수는 다음과 같다

=> M / (K+1) * K + M % (K+1)

 

위의 식을 통해 가장 큰 수가 더해지는 횟수를 구하고, 이를 이용해서 두번째로 큰 수가 더해지는 횟수도 구하면 된다!

 

C++)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,m,k, first, second;
    int tmp;
    int result=0, count =0;
    vector<int> x;
    
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        x.push_back(tmp);
    }
    
    sort(x.begin(),x.end());
    
    first=x[n-1];
    second=x[n-2];
    
    count = m/(k+1)*k; //가장 큰 수가 더해지는 횟수
    count += m%(k+1); // 가장 큰 수가 추가로 더해지는 횟수
    
    result += (count)*first; // 가장 큰 수 더하기
    result += (m-count)*second; //두 번째로 큰 수 더하기
    
    cout << '\n'<< result;
    return 0;
}

이번엔 c++ vector로 풀어봤다

sort(x.begin(), x.end()) 랑 x.push_back을 아직도 헷갈려해서 좀 민망하지만 벡터도 나쁘지않다!

암튼 이런식으로 하면 시간 초과 문제는 걱정 안해도 된다

중요한건 뭐다? 반복되는 수열 찾기!!

 

 

---

2일차 딴딴 코테공부도 끝!

빠잉!