[풀이 피드백] 큰 수의 법칙 2025-11-13 #1
Description
1. 문제 정보
- 플랫폼: 이것이 코딩테스트다
- 문제 링크: X
- 난이도/태그: 그리디
2. 제출 코드
- 저장소/브랜치: 큰 수의 법칙.py
3. 개선 포인트
같은 값이라도 서로 다른 인덱스면 다른 수로 취급된다는 점을 놓쳐서, 최댓값과 같은 값을 가진 원소를 두 번째로 사용하지 못한다고 생각했다.
결과적으로 second가 제대로 채워지지 않는 케이스(예: 모든 원소가 같은 값, 음수 포함)에서 합이 틀렸다.
패턴 계산: first K회 + second 1회를 반복하는 패턴을 수학적으로 계산해 count = (m // (k + 1)) * k + (m % (k + 1))로 한 번에 구해 시간 복잡도를 O(n log n) + O(1)로 낮추는 게 포인트
반복되는 수열의 길이는 k+1
따라서 수열이 반복되는 횟수는 m // (k+1)
여기에 k를 곱하면 가장 큰 수가 등장하는 횟수
그리고 m이 k+1로 나누어 떨어지지 않을 때 등장하는 가장 큰 수의 개수는 m % (k+1)
그래서 가장 큰 수는 count개 더해짐.
그럼 두 번째로 큰 수는? m - count개 더해지겠음.
근데, 그러면 수열 한 묶음의 합을 구한 후에 m // (k+1) 개를 곱해주고, m % (k+1) 개 만큼 가장 큰 수를 더해줄 수도 있지 않을까??
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
numbers = list(map(int, input().split()))
# 주어진 수들을 M번 더해서 가장 큰 수를 만드는 법칙인데 한 수를 K번 초과해서 더할 수 없다.
numbers.sort()
first = numbers[-1]
second = numbers[-2]
hap = first * k + second
result = hap * (m // (k+1)) + first * (m % (k+1))
print(result)