큰수의 법칙 문제 1 그리드

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

문제

숫자의 개수(n), 더할횟수(m), 최대 반복횟수(k) 를 입력을 받고 값을 출력하기

예를 들어서 5,8,3이 들어오게 되고 배열이 2,3,4,5,6이라고 가정하면

6+6+6+5+6+6+6+5 총 8번을 더해서 가장 큰 수를 구하는데 3번이상 연속으로 더하면 안되는 조건

n, m, k = map(int, input().split())
data = list(map(int,input().split()))
#데이터 입력

data.sort()
first = data[n-1]
second = data[n-2]
#리스트 정렬 -> 첫번째와 두번째로 큰 수 찾기

여기까지하면 가장큰 값과 두번째로 큰 값을 구할 수 있다.

data.sort()할때 ()빼먹으시면 안됩니다.

풀이 1

result = 0
while(True):    
    for i in range(k): #가장 큰수를 k번 더하고
        if m == 0: #m이 0이면 탈출
            break
        result += first 
        m-=1       #더할때마다 m에서 1빼기
    if m==0:
        break
    result += second
    m -= 1

보통 이런 코드를 짤때는 반복횟수를 결정하기보다 무한으로 돌리고

특정 조건을 만족하면 무한루프를 빠져나오는것이 편리합니다.

일단 첫번째 for문에서는 최대 더하는 횟수를 계산하며 그때마다 가장 큰값인 first를 더해줍니다.

그리고 다 했다면 다음으로 두번째로 큰 수를 한번 더하고 진행을 하는데 안쪽 for이나 마지막이나 최대 더하는 횟수를 1씩 차감을 하는 것을 볼 수 있습니다. 그러다가 m이 0이 되는 순간에는 break를 만나서 빠져나오게 됩니다.

그런데 여기서 아이디어를 하나 얻을 수 있습니다.

위 식에 따르면 6665 6665가 반복되는데 묶음으로 계산을 할 수 있겠지요

그리고 묶음의 나머지 개수에다가 최대 숫자를 곱해서 더하면 바로 구할 수 있겠다는 생각도 자연스럽게 드네요

아니면 가장 큰 수가 더해지는 횟수를 계산을 하고 (전체 횟수 - 가장 큰 횟수)는 두번째로 큰 수의 횟수가 될 수도 있겠네요

풀이2

count = int(m/(k+1))*k
count += m%(k+1)

result = 0
result += (count)*first
result += (m-count)*second

일단 한세트가 k+1인것은 이해를 하실 겁니다. 그러면 2세트라고 가정을 하면 여기에다가 최대 반복횟수 k를 곱하면 기본적으로 2*k번만큼의 큰 수가 들어가게 되고

여기에서 나머지 만큼의 큰수가 추가적으로 들어가게 됩니다.

이를 이용하면 최대숫자와 두번째 큰 숫자가 얼마나 들어가는지 알 수 있습니다.

결과역시 똑같이 나옵니다.