큰 수의 법칙

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

분류:: 그리디

 

1. 문제 이해 및 해결과정

1번 풀이 - 가장 큰 수와 그 다음 큰 수 저장해놓고  - k가 될때까지는 큰 수 더하고 그 다음 큰 수 더하고를 반복한다 2번 풀이. 반복되는 수열에 대해서 파악하기 - ex)  5 8 3  /n 2 4 5 4 6일때  6 6 6 5 / 6 6 6 5 반복  - m//(k+1) 8//4 => 2, 2는 수열의 반복 횟수 2*k= 전체에서 가장큰 수가 몇번 나오는지 - m%(k+1) => 수열이 딱 안나누어 떨어질 경우 추가 되는 가장 큰 수의 개수  => sum = m//(k+1)*k + m%(k+1)

 

2. 풀이방법

- 1. 그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

import sys
sys.stdin = open("input.txt","r")
n,m,k=map(int,input().split())
li=list(map(int,input().split()))
li.sort(reverse=1)
num1=li[0]
num2=li[1]
cnt=0
sum=0
for i in range(0,m):
    if cnt==k:
        cnt=0
        sum+=num2
    else:
        cnt+=1
        sum+=num1
print(sum)

- 2. 그리디 : 수열이용

#큰 수의 법칙
#
import sys
sys.stdin = open("input.txt","r")
n,m,k=map(int,input().split())
li=list(map(int,input().split()))
li.sort()
num1=li[n-1]
num2=li[n-2]
cnt=m//(k+1)*k
cnt+=m%(k+1) #수열이 패턴 수대로 안나누어 떨어질 경우

sum=0
sum+=cnt*num1
sum+=(m-cnt)*num2
print(sum)

 

 

3. 오답원인

 

4. 알게된 점

- 수열을 이용해서 풀이하는 것은 생각못했다

- 굳이 reverse해서 sort할 필요없이 전체 길이에서 빼줘도 된다

- 그리디가 왜 그리디인가,,,