[이것이 코딩 테스트다] 그리디 <2. 큰 수의 법칙>

📚[실전 문제] 큰 수의 법칙

[문제]

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

❗ 예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5 인 46이 된다.

[입력 조건]

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

[출력 조건]

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

[입력 예시]

5 8 3
2 4 5 4 6

[출력 예시]

46

🔍[단순하게 푸는 답안 예시]

이 문제를 해결하기 위해 일단 입력값 중에서 가장 큰 수(first)와 두 번째로 큰 수(second)만 저장하면 된다.

연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산'을 반복하면 되기 때문.

이렇게 단순하게 접근하여 표현한 소스코드는 아래와 같다.

n, m, k = map(int,input().split())
data = list(map(int,input().split()))

data.sort(reverse=True) # 입력받은 data를 내림차순으로 정렬 
first = data[0] # 제일 큰 수
second = data[1] # 두번째로 큰 수

result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1

print(result)

🔍[반복되는 수열에 접근하여 푼 답안 예시]

반복되는 수열에 대해 파악했을 때 가장 큰 수(first)와 두 번째로 큰 수(second)가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

앞서 보였던 입력 예시를 예로 들었을 때 수열{6,6,6,5}가 반복된다. (first = 6, second = 5)

그렇다면 반복되는 수열의 길이는 바로 (K+1)로 위의 예시를 통해서는 4가 된다. (K = 3)

따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.

다시 여기에 K를 곱하면 가장 큰 수가 등장하는 횟수가 된다.

따라서 가장 큰 수가 더해지는 횟수를 구한 다음, 이를 이용하여 두 번째로 큰 수가 더해지는 횟수까지 구할 수 있는 것이다.

이를 토대로 파이썬을 이용하여 답안을 작성하면 다음과 같다.

n ,m , k = map(int,input().split())

data = list(map(int,input().split()))

data.sort(reverse=True)
first = data[0]
second = data[1]

count = int(m / (k+1)) * k
count += m % (k+1)

print(count)

result = 0
result += (count) * first
result += (m - count) * second

print(result)

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.