# CHAPTER 03. 큰 수의 법칙

🎫 큰 수의 법칙

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

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 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 + 4 + 4 + 4인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

🎁입력 조건

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

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

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

✨출력 조건

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

🎄입력 예시

5 8 3

2 4 5 4 6

🎨출력 예시

46

---

🎃 핵심 아이디어

N 개의 숫자들이 주어지고, 각각을 M번 더하여 최고로 큰 수를 만들고자 한다. ( 단, 특정한 인덱스에 해당하는 수가 연속해서 K 번을 초과하여 더해질 수는 없다.)

5 8 3
2 4 5 4 6

해당 입력을 예시로 들어보면, 큰 수를 만들기 위해 당연히 입력한 숫자열[2,4,5,4,6] 중 가장 큰 숫자를 최대한 많이 더하고자 한다. 다만, 중복해서 더하는 것은 총 3번까지만 가능하므로 2번째로 큰 숫자를 찾은 다음 중복 조건에서 겨우 벗어나게 더해주면 되지 않을까?
그러므로 6+6+6+5+6+6+6+5 와 같은 방안이 최고로 큰 수이다! 이를 자세히 보면,
(6+6+6+5)+(6+6+6+5) 와 같이 중복 수열을 볼 수 있다.
중복 수열의 길이는 K+1 이다.
조금 더 생각해보면, 숫자열을 입력받고 for 문을 돌리면서 index 가 k의 배수이면 그 때에만 " 두 번째로 큰 수" 를 더해주고, index 가 k의 배수가 아니면 "첫 번째로 큰 수"를 더해주면 된다.

🎢 구현 A안.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  int n,m,k;

  cin>>n>>m>>k;
  vector<int> v;

  for(int i = 0 ; i < n ; i++)
  {
    int input;
    cin >> input;
    v.push_back(input);
  }

  sort(v.begin(),v.end());
  int first = v[n-1];
  int second = v[n-2];

  int ans = 0;

  for (int i = 1 ; i <= m ; i++)
  {
    if( i%k == 0)
      ans += second;
    else
      ans += first;
  }

  cout << ans;

  return 0;
}

이렇게 코드를 짜도, 주어진 입력에 대해서 아무런 문제 없이 잘 작동한다. 하지만 만일 시간 제한이 1초로 지정된 경우, 구현 A안은 시간 초과가 발생할 것이다. 만일, M 100억 이상 커지게 된다면 1초 이상의 시간이 걸릴 것이 자명하기 때문이다!
그렇다면 보다 최적화할 수 있는 방법은 없을까...??

위에서 예시를 들었듯이, 입력이 아래와 같다면

5 8 3
2 4 5 4 6

(6+6+6+5)+(6+6+6+5) 와 같이 중복 수열을 볼 수 있고, 어떠한 경우이든 간에 중복 수열의 길이를 논하면, K+1임은 자명하다. 그렇다면 최고로 큰 숫자가 더해지는 횟수를 만약 알 수 있다면, 반복문을 굳이 돌지 않아도 출력값을 쉽게 알 수 있을 것이다. (핵심)
길이가 K+1 인 중복 수열에서는 중복 수열 하나 당 K번 만큼 가장 큰 수가 더해질 것이다. 그말은 즉슨 중복 수열의 길이 K+1 에 대하여, M/(K+1) 연산을 통해 M 번의 덧셈 과정에서 중복 수열이 몇 번 나타나는 지 알 수 있고, 이에 K를 곱해주면 그것이 바로 최고로 큰 수가 더해지는 횟수가 될 것이다. 만약! M/(K+1)이 안나누어 떨어질 수도 있다. 이러한 경우에는 M 을 K+1 로 나누었을 때 나머지가 발생하면, 그 나머지 만큼 최고로 큰 수가 더 더해지는 것이다.
즉, 가장 큰 수가 더해지는 횟수를 Count 라고 정의하면, count = k*(m/(k+1))+(m%(k+1)) 이고, 두 번째로 가장 큰 수가 더해지는 횟수는 m - count 일 것이다.

반복문을 돌지 않더라도 충분히 합을 구해낼 수 있으므로, m이 수십억이라도 하더라도 시간 제한 조건을 무리없이 통과해낼 수 있을 것이다!

🎗구현 B안.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  int n,m,k;

  cin>>n>>m>>k;
  vector<int> v;

  for(int i = 0 ; i < n ; i++)
  {
    int input;
    cin >> input;
    v.push_back(input);
  }

  sort(v.begin(),v.end());
  int first = v[n-1];
  int second = v[n-2];

  int ans = 0 ;
  int count = (m/(k+1))*k+m%(k+1);
  ans += count * first;
  
  count = (m/(k+1));
  ans += count * second;

  cout << ans;

  return 0;
}

---

해당 내용은 '이것이 취업을 위한 코딩 테스트다 WITH 파이썬 (나동빈)'을 공부하며 기록하기 위해 작성한 글 입니다.

---