[그리디] 큰 수의 법칙 (실전문제, 이것이 코딩테스트다 with 파이썬)

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형
• 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형

 

문제

 

풀이1 : 기본적인 풀이

# 변수 : N 숫자 개수, M 더하는 횟수, K 연속 횟수, result 합
# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
result = 0

# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 입력받은 수들 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수

while True: # 무한 루프
    for i in range(k): # 가장 큰 수를 K번 더하기
        if m == 0: # M이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 1씩 빼기
    if m == 0 # M이 0이라면 반복문 탈출
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기
    
print(result) # 최종 답안 출력

 

해석

변수 : N 숫자 개수, M 더하는 횟수, K 연속 횟수, result 합

 

1. 입력받은 수를 내림차순으로 정렬 : 큰 수가 앞으로 오도록

2. 가장 큰 수를 K번 더하고, M의 횟수 차감

3. 두번째로 큰 수를 K+1번째에 1번 더하고, M의 횟수 차감

4. M == 0 이 되면 끝

 

한계점 : M의 크기가 100억 이상으로 커지면  O(N)의 시간 복잡도로 인해 시간 초과 판정 위험

 

cf) 시간 복잡도

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘 설계
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘 설계
• N의 범위가 100,000(10만)인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘 설계
• N의 범위가 10,000,000(1000만)인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계

 

풀이2 : 시간 복잡도를 줄인 버전

# 변수 : N 숫자 개수, M 더하는 횟수, K 연속 횟수, result 합
# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
result = 0

# 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 숫자 개수, M 더하는 횟수, K 연속 횟수, result 합

 

1. 입력받은 수를 내림차순으로 정렬 : 큰 수가 앞으로 오도록

2. 한번에 가장 큰 수가 더해지는 횟수(count)를 계산 : 알고리즘 참고

3. 가장 큰 수를 count 만큼 더함

4. 두번째로 큰 수를 m-count 만큼 더함