[이코테] CH03 그리디 실전문제 큰수의법칙

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9

N,M,K = map(int,sys.stdin.readline().split())


x = list(map(int,sys.stdin.readline().split()))
x.sort(reverse = True)
max = x[0]
max2 = x[1]
sum = 0
index = 0
print(x)
for _ in range(M):
    index +=1
    if index % K == 0:
        sum+=max2
    else:
        sum += max

print(sum)

일단 이게 내가 처음 짠 코드

k번은 가장 큰 숫자, 1번은 두번째로 큰 숫자 더하는 식으로 했는데

M이 커질수록 시간복잡도가 커진다 : O(M)

 

그러므로 시간복잡도를 더 효율적으로 할 수 있는 방법이 있다 ! (for문을 사용하지 않고도 해결할 수 있음)

 

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9

N,M,K = map(int,sys.stdin.readline().split())


x = list(map(int,sys.stdin.readline().split()))
x.sort(reverse = True)
max = x[0]
max2 = x[1]
sum = 0
count = int(M/(K+1)) * K
# 여기서 K+1은 수열의 길이. 가장 큰 수가 K번 / 두번째 큰 수가 1번 등장해서 총 K+1의 길이인 수열
# int(M/K+1)은 전체 수열의 반복 횟수. 거기에 k를 곱해주면 가장 큰 수가 나오는 총 횟수가 나온다.
count += M % (K+1)
# 그리고 나머지 숫자를 더해줘야 한다 (M/(K+1))이 나누어떨어지지 않는 경우 고려
sum += count * max 
# max는 가장 큰 수, 카운트는 가장 큰 숫자가 나오는 횟수
sum += (M-count) * max2
#반복은 총 M번이므로 M-count가 2번째 큰 숫자가 나오는 횟수
print(sum)

이렇게 생각할 수 있도록

여러가지 문제를 풀어봐야겠다고 느꼈다.

쉬운 문제여도 얻어갈게 확실히 있다는걸 느꼈다