[이코테] 큰 수의 법칙

https://github.com/ndb796/python-for-coding-test/blob/master/3/2.py

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

 

1. 해결방법

그리디 문제이다.

본인은 반복문으로 풀었지만 좀 더 효율적인 방법은 가장 큰 수와 두 번째로 큰 수밖에 사용하지 않는다는 부분을 파악해야한다.
가장 큰 수를 K번 만큼 반복하고, 다음 두 번째로 큰 수를 한번 더해주면 된다.

 

 

2. 정답코드

(1) 단순하게 푸는 방법

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
numbers = list(map(int, input().split()))

numbers.sort(reverse=True)

answer = 0
count = 0
idx = 0
for i in range(1, M + 1):
    if count == K:
        idx += 1

    answer += numbers[idx]
    if count == K:
        idx -= 1
        count = 0
    count += 1

print(answer)

(2) 수학적으로 푸는 방법

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
numbers = list(map(int, input().split()))

numbers.sort(reverse=True)

answer = 0
first = numbers[0]
second = numbers[1]

count_s = (M // K)
count_f = M - count_s

print(first * count_f + second * count_s)