[코딩테스트 python] 그리디 Greedy ; 큰수의 법칙

 

#저서 : 이것이 취업을 위한 코딩테스트다 with 파이썬

#기출 : 2019 국가 교육기관 코딩 테스트

# 문제

주어진 수들을 M번 더하여 가장 큰 수 만들기.

# 제한사항

• 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번 초과하여 더해질 수 없음.
• 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주
• 첫째 줄 : N(2<= N <= 1,000) M(1<= M <= 10,000) K(1<= K <= 10,000) >> 공백으로 구분
• 둘째 줄 : N개의 자연수 >> 공백으로 구분. 단, 각각의 자연수는 1 ~ 10,000의 수
• 입력으로 주어지는 K는 항상 M보다 작거나 같다

 

처음 풀이

n, m, k = map(int, input().split())
n_arr = sorted(list(map(int, input().split())), reverse=True)

answer = 0
for i in range(1, m+1):
  if i%k == 0:
    answer += n_arr[1]
  else:
    answer += n_arr[0]

print(answer)

이 경우, M의 크기가 100억이 넘어가면 시간 초과!
반복되는 수열을 파악해서 시각복잡도를 줄여함.

> k의 배수의 개수 만큼 1번이 더해지고, 나머지는 0번이 더해짐.
> m // k  == 나눈 몫 만큼 가장 큰 수 1번이 더해짐

 

수정 풀이

n, m, k = map(int, input().split())
n_arr = sorted(list(map(int, input().split())), reverse=True)

answer = n_arr[0]*(m-m//k)+n_arr[1]*(m//k)
print(answer)

 => 반복문도 좋지만 반복되는 수열을 먼저 찾아보는 수학적 아이디어를 생각해보는 것이 효율적!!