[그리디 2] 큰 수의 법칙

이 문제는 가장 좋은 것을 선택하여 풀이가 가능한 문제이기 때문에 그리디 문제이다.

이 문제를 해결하기 위해서는 가장 큰 수가 몇 개인지 확인하는 작업이 중요하다. 먼저 두 개의 작은 예제를 풀어 보고, 일반화 과정을 거칠 것이다.

미니 예제 1. 가장 큰 수가 1개인 경우

1. 문제 설명하기.

2,4,5,4,6으로 이루어진 배열이 있다. M=8이고, K=3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속하여 3번까지 더해질 수 있고, 총 8번 더할 수 있다는 의미이다.

2. 문제 해결하기.

손으로 풀이하면, 6+6+6+5+6+6+6+5=46이 나온다.
이 문제는 가장 큰 수가 1개인 문제이다. 그러므로 가장 큰 수와 두 번째로 큰 수를 구하여 풀이하면 된다.

Step 1. 반복문을 돌려서 가장 큰 수를 찾는다.

중요한 점은 가장 큰 수를 0 이라고 두고, 반복이 진행되면서 가장 큰 수가 갱신되는 방식을 떠올려야 한다.

Step 2. 두 번째로 큰 숫자를 찾는 사용자 함수 만들기.

이미 가장 큰 수를 구했기 때문에, 반복하여 돌리면서 가장 큰 수보다 작은 값을 찾으면 구할 수 있다. 주의할 점은 초기값도 반복문이 돌아감에 따라 변경해야 한다.

Step 3. M번의 반복문을 돌려 조건에 맞게 더해주기.

M, K를 이용하여 조건에 맞게 더해준다. 이 때 주의할 점은 두 번째로 큰 숫자를 더한 뒤에 iter=0으로 재설정하여 다시 if 조건문으로 들어갈 수 있게 만들어준다.

위와 같은 과정을 모두 수행하게 된다면 원하는 값을 얻어낼 수 있다.

# [2,4,5,4,6], M=8, K=3인 경우 -> 답 46 나와야 한다.

array=[2,4,5,4,6]

max_sum=0
max_value=0

M=8
K=3
iter=0

# Step 1. 가장 큰 숫자 찾기.

for idx in range(len(array)):
    
    """
    print(idx) # 배열의 인덱스
    print(array[idx]) # 배열의 각각의 값
    """
    
    if array[idx] >= max_value:
        max_value=array[idx] # 가장 큰 값을 찾음.

# Step 2. 두 번째로 큰 숫자 찾는 사용자 정의 함수를 만들어서 원하는 숫자 찾아주기.
        
def secondMax(arr, max_val):
    init=0 # 초기값
    for val in arr:
        if (val>init) & (val<max_val):
            second_max_val=val
            init=val  # (주의) 초기값도 변경해줘야 한다. 아니면 계속 0으로 유지된다.
            
    return second_max_val
    
second_max_value=secondMax(array, max_value) # 두 번째로 큰 숫자 = second_max_value

# Step 3. M번 반복문을 돌려서 조건에 맞게 더해주기. (탐욕법으로 해결 가능 , "그리디 문제")
    
for iter_count in range(M):
    if iter < K:
        max_sum+=max_value
        iter+=1
    else:
        max_sum+=second_max_value
        iter=0 # (주의) iter=0으로 재설정하여 다시 if 조건문으로 갈 수 있도록 만들어 준다.

print(max_sum)

미니 예제 2. 가장 큰 수가 2개 이상인 경우

1. 문제 설명하기.

3,4,3,4,3으로 이루어진 배열이 있고, M=7, K=2라고 가정하자. 위의 경우와 다르게 가장 큰 수가 2개 이상이기 때문에 두 번째로 큰 수를 찾을 필요가 없가.

2. 문제 해결하기.

Step 1. 반복문을 돌려 가장 큰 수를 찾는다.

Step 2. 가장 큰 수가 2개 이상이기 때문에 두 번째로 큰 수는 구하지 않아도 된다. 대신 가장 큰 수의 인덱스를 구해야 한다.

Step 3. M번의 반복문을 돌려 조건에 맞게 더해주기.

# [3,4,3,4,3], M=7, K=2인 경우 -> 답 28 나와야 한다.

array=[3,4,3,4,3]

max_sum=0
max_value=0
max_idx_list=[]

M=7
K=2
iter=0

# Step 1. 가장 큰 숫자 찾기.

for idx in range(len(array)):
    
    """
    print(idx) # 배열의 인덱스
    print(array[idx]) # 배열의 각각의 값
    """
    
    if array[idx] >= max_value:
        max_value=array[idx] # 가장 큰 값을 찾음.
        
for idx in range(len(array)):
    if array[idx]==max_value:
        max_idx_list.append(idx)
        
# print(max_idx_list) 가장 큰 값의 인덱스를 찾음.
 
#  Step 2. 가장 큰 값의 인덱스를 이용하여 조건에 맞게 더하기.

for iter_count in range(M):
    if iter < K:
        max_sum+=array[max_idx_list[0]]
        iter+=1
    else:
        max_sum+=array[max_idx_list[1]]
        iter=0 # (주의) iter=0으로 재설정하여 다시 if 조건문으로 갈 수 있도록 만들어 준다.

print(max_sum)

일반화

map()을 이용하여 입력받은 숫자를 정수로 받아올 수 있다.

Step 1. 가장 큰 수를 찾고, 가장 큰 수가 몇 개가 있는지 살펴보기. 그리고 가장 큰 수를 가진 인덱스를 리스트에 담기.

Step 2. 가장 큰 수가 1개인 경우, 두 번째로 큰 수를 구하고 조건에 맞게 합산한다.

Step 3. 가장 큰 수가 2개 이상인 경우, 조건에 맞게 합산한다. 이 경우 random 모듈을 불러와서 서로 다른 인덱스를 갖는 가장 큰 수를 더해줘야 한다.

• choice : 중복 허용 O
• sample : 중복 허용 X (우리는 다른 인덱스 가진 값을 사용 원함. 따라서 비복원 추출로 가져와야 한다.)

# 일반화

import random

M, K=map(int, input().split()) # map 이용하여 정수로 변환하기.
array=list(map(int, input().split()))

max_sum=0
max_value=0
max_idx_list=[]
iter=0

# Step 1. 가장 큰 수를 찾고, 가장 큰 수가 몇 개 있는지 파악하는 것이 중요하다.

for idx in range(len(array)):
    if array[idx] >= max_value:
        max_value=array[idx]
        
for idx in range(len(array)):
    if array[idx]==max_value:
        max_idx_list.append(idx)
        
# print(max_idx_list) 가장 큰 수를 가진 인덱스를 찾을 수 있다.


# Step 2. 가장 큰 수가 1개인 경우, 두번째로 큰 수를 구하고 조건에 맞게 합산해야 한다.

if len(max_idx_list)==1: # 가장 큰 수가 1개인 경우
    
    def secondMax(arr, max_val):
        init=0 # 초기값
        for val in arr:
            if (val>init) & (val<max_val):
                second_max_val=val
                init=val # (주의) 초기값도 변경해줘야 한다. 아니면 계속 0으로 유지된다.
        return second_max_val
    
    second_max_value=secondMax(array, max_value) # 두 번째로 큰 숫자 = second_max_value
    
    for iter_count in range(M):
        if iter < K:
            max_sum+=max_value
            iter+=1
        else:
            max_sum+=second_max_value
            iter=0 # (주의) iter=0으로 재설정하여 다시 if 조건문으로 갈 수 있도록 만들어 준다.

# Step 3. 가장 큰 수가 2개 이상인 경우, 조건에 맞게 합산하기.
        
else: # 가장 큰 수가 2개 이상인 경우
    sample_idx=random.sample(max_idx_list, 2) # 랜덤하게 2개 뽑는다. (중복 허용 X), 중복 허용 : choice
    for iter_count in range(M):
        if iter < K:
            max_sum+=array[sample_idx[0]]
            iter+=1
        else:
            max_sum+=array[sample_idx[1]]
            iter=0
            
print(max_sum)

최적의 일반화

위의 과정은 나의 사고 흐름대로 풀어보았다. 최적의 방법으로 일반화 시켜보도록 하겠다.

최적의 일반화 1

기준	나의 풀이	최적의 풀이
값 입력받기	m, k, array	n, m, k, array
가장 큰 수와 두 번째로 큰 수 찾기	반복문과 인덱스 이용하여 찾음	sort() 정렬 함수와 인덱스 이용
더하는 규칙	n으로 반복문 돌리기	무한 반복문과 k으로 반복문 돌리기

알고리즘 설명하기.

check 1. k번 돌리면서 가장 큰 수를 더하고 m을 하나 차감하기.
check 2. m이 0인 경우에는 반복문을 빠져나가거나 끝내야 한다.
check 3. k번 다 돌리고 m을 다 사용하지 않는 경우 두 번째로 큰 수를 더하고 m을 하나 차감하기.

n,m,k = map(int, input().split()) # n : array 안에 들어있는 원소의 개수
array = list(map(int, input().split())) # list로 반드시 변경해주기.

array.sort() # sorted() : 변경 X vs sort() : 변경 O

first=array[n-1] # n이 인덱스로 사용된다. 가장 큰 수
second=array[n-2] # 두 번째로 가장 큰 수

result=0

### 알고리즘 ###

"""

step 0. k번 돌리면서 가장 큰 수를 더해주는데, 그 순간 m을 하나씩 차감해야 된다. 
step 1. 그 안에서 m이 0이 되면 빠져나가야 된다.
step 2. 만약 빠져나가도 m이 0이면 그대로 결과 출력하기.
step 3. k번 다 돌리면 두 번째로 큰 수를 더해줘야 된다. 그리고 m을 하나씩 차감해야 된다.

"""

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)

최적의 일반화 2

M이 엄청나게 큰 수인 경우 유용한 방법이다. (예를 들어 M이 100억 이상이다.) 1번과 다르게 수열을 이용하여 푼 문제인데 수열이 왜 그렇게 나왔는지 이해가 안 간다. 더 고민해보기.