[03그리디] 3-2 큰 수의 법칙(p92~p95)

[예제3-2]

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

예를들어 순서대로 2, 4, 5, 4, 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인 28이 도출된다.

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

 

[입력 조건]

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

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

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

 

[출력 조건]

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

 

[입력 예시]

5 8 3
2 4 5 4 6

 

[출력 예시]

46

 

[코어 아이디어]

 - 입력 값 중 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

 - 연속으로 더할 수 있는 횟수가 K번이므로, 가장 큰 수를 K번 더하고 두번째로 큰 수를 한번 더하는 연산을 반복하는게 핵심

 

[솔루션(단순 Ver.)]

# N은 배열의 크기
# M은 숫자가 더해지는 횟수
# K는 연속으로 더할 수 있는 횟수
# data는 실제 배열의 원소

# 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):
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0:
        break
    result += second
    m -= 1

print(result)

 

[코드 상세 분석(단순 Ver.)]

 

1. 각각의 변수에, 공백을 구분자로 한번에 입력받는법

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

 

2. 여러 수를 한번에 받아 리스트형태로 저장

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

 - 아까 map(int, input().split())을 list로 감싸주면 된다.

 

3. 내림차순 정렬 후 가장 큰 수와 두번째로 큰 수를 변수에 저장

data.sort() #내림차순 정렬 O(NlogN)

first = data[n-1] #내림차순 정렬이므로 맨 뒤에꺼가 제일 큰거
second = data[n-2]

 

4. while문 분석

# n은 배열의 크기
# m은 총 숫자가 더해지는 횟수
# k는 연속으로 최대 더할 수 있는 횟수

while True:
    for i in range(k): #가장 큰 수를 K번 더하기 위한 for문
        if m == 0: #총 더할 수 있는 횟수가 0일때 탈출
            break
        result += first #for문 만큼 result에 가장 큰 수를 더함
        m -= 1 # K에 대한 for문이 한 사이클 돌때마다 횟수 차감
    if m == 0: #for문 밖의 if문: 다음번 큰 수를 위함(즉 second를 위함)
        break
    result += second #second는 한번만 더하면 되기때문에 별도의 for문 불필요
    m -= 1 #총 숫자가 더해지는 횟수는 차감해야함
    
print(result) #결과출력

 

 

[솔루션(로직 Ver.)]

M이 10,000 이하일때는 위의 단순 Ver로 풀이가 가능하지만, 만약 M의 크기가 100억 이상일때는 시간초과가 뜬다.

수학적 아이디어를 사용해 더 효율적으로 문제를 해결해보자.

M이 8, K가 3이고,

N이 5일 때 입력값이 아래와 같이 주어졌다.

2 4 5 4 6

 

 

이 때 가장 큰 수와 두번째로 큰 수를 선택하면

 - 가장 큰 수 : 6

 - 두번째로 큰 수 : 5

 

이후, K가 3이므로,

(6, 6, 6, 5) + (6, 6, 6, 5)가 된다. 정답은 46

 

여기서, 반복되는 수열에 대해 좀 더 자세히 파악을 해보자.

위의 예시에서는 (6, 6, 6, 5)가 반복된다. 이 때 수열의 길이는 (K+1)로 위의 예시에서는 4가 된다.

 

따라서, M을 (K+1)로 나누었을때의 몫이 수열이 반복되는 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 됨.

단, M이 (K+1)로 나눠 떨어지지 않는경우도 생각해야하는데, 이 경우에는 M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해져 이것도 같이 고려해줘야한다.
즉, 가장 큰 수 가 더해지는 횟수는

(int(M / (K + 1)) * K) + (M % (K + 1))

이 될것이다.

 

그래서 전체 코드는

# N은 배열의 크기
# M은 숫자가 더해지는 횟수
# K는 연속으로 더할 수 있는 횟수
# data는 실제 배열의 원소

# 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]  # 두번째로 큰 수

#가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += count * first #가장 큰 수 더하기
result += (m-count) * second #두 번째로 큰 수 더하기

print(result)

 

 

입력값이 다음과 같다고 하자:

 

N = 5, M = 8, K = 3 data = [2, 4, 5, 4, 6]

---

1. 정렬

 

data.sort() → [2, 4, 4, 5, 6]

가장 큰 수 = 6
두 번째 큰 수 = 5

---

2. 더하기 규칙

K = 3이므로
→ 가장 큰 수(6)는 최대 3번까지만 연속으로 더할 수 있다.
→ 3번 더한 뒤에는 반드시 한 번 다른 수(5)를 더해야 한다.

즉, 반복 패턴은 이렇게 된다:

 

[6, 6, 6, 5] ← 이게 한 묶음 (4번)

---

3. 전체 횟수 M = 8일 때

이 패턴을 몇 번 반복할 수 있는가?

• 한 묶음의 길이는 k + 1 = 4
• 총 횟수 M = 8

→ 8 // 4 = 2
즉, 이 패턴이 두 번 완전히 반복됨
그 안에서 큰 수(6)는 각 묶음당 3번씩 나오므로
(2묶음) × (3번) = 6번

이게 바로 식의 첫 부분

 

(m // (k + 1)) * k = (8 // 4) * 3 = 6

---

4. 남은 횟수 계산

총 8번 중 2묶음(4×2=8)을 사용했으니 남은 횟수는 0
하지만 일반적으로 M이 패턴으로 나누어떨어지지 않으면 남는 횟수가 생긴다.
그때 남은 횟수만큼은 가장 큰 수(6)를 계속 더할 수 있다.

즉, m % (k + 1)

이 예시에서는

8 % 4 = 0

→ 남은 횟수 없음.

---

5. 합치면

 

count = (m // (k + 1)) * k + (m % (k + 1)) = (8 // 4)*3 + (8 % 4) = 6 + 0 = 6

즉, 가장 큰 수(6)는 총 6번 더해진다.
남은 2번은 두 번째 큰 수(5)가 더해진다.

---

6. 전체 더하기 순서 (직접 나열)

 

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5

= 46