[그리디] - 큰수의 법칙

큰수의 법칙

- 다양한 수로 이루어진  배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙 

- 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

- 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른것으로 간주

 

입력 예시)

5 8 3

2 4 5 4 6

 

출력 예시)

46

 

나의 코드

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

arr=list(map(int,input().split()))
arr.sort(reverse=True)

s=0
cnt=0

while True: 
    for _ in range(k):
        if cnt==m:
            print(s)
            break
        s+=arr[0]
        cnt+=1
     
    if cnt==m:
            print(s)
            break

    s+=arr[1]
    cnt+=1

전형적인 그리디 유형이다.

실질적으로 사용되는것은 가장큰 수와 가장 작은수이다.

내림차순으로 정렬한뒤 첫번째 인덱스(가장큰수)를 3번 더하고 두번째 인덱스를 1번 더해주는것을 반복하며 그 횟수가 M인경우 종료하면 끝이다..!

 

처음 while 내부의 for문에서 break가 되면 코드가 종료되고 끝이 나길 원해 함수로 작성할까 하다가 break를 해야하는 분기 처리의 위치를 적절히 추가 및 재배치 해서 해결 하였다.

 

 

 

 

 

 

정답 코드

# 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 = m // (k + 1) * k       # M이 k+1로 나누어 떨어질때
count += m % (k + 1)          # M이 k+1로 나누어 떨어지지 않을 때

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

print(result) # 최종 답안 출력

 

나의 코드로 풀어도 위 문제에서는 괜찮지만 M의 입력값이 10억이상인 경우에는 시간 초과가 발생한다

 

더욱 시간 초과를 줄이기 위해서는 반복되는 수열에 대해 파악해야 한다 !

반복 되는 수열의 길이 : K+1

수열이 반복되는 횟수 : M//(K+1)

가장큰수의 갯수 :M//(K+1)*K [나누어떨어질때 ] +  M%(K+1)[ 나누어 떨어지지 않을 때]