[파이썬] 이코테 - 그리디 알고리즘, 큰 수의 법칙(실전문제)

그리디 알고리즘 (Greedy Algorithm)

• 그리디란 '탐욕'이라는 의미
  즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

✔[문제 설명]

• 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
  배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어질 때 결과를 출력해라.

[입력 조건]

• 첫째 줄에 N(2 <= N <= 1000),M(1 <= M <=10,000),K(1 <= K <=10,000)의 자연수, 자연수는 공백으로 구분
• K <= M
• 둘째 줄에 N개의 자연수가 주어지고, 공백 구분(1 <= 자연수 <=10,000)

ex)
5 8 3
2 4 5 4 6 -> 46 출력

[작성 코드]

n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort() #정렬 
first = data[n-1]
second = data[n-2]

result = 0 

while True:
    for i in range(k):
        if m == 0:
            break
          
        result += first
        m -= 
        
    if m == 0:
        break
    result += second
    m -= 1

print(result)

입력 : 5 8 3 \n 2 4 5 4 6

출력 : 46

• for 문까지는 스스로 생각하여 작성할 수 있었지만, 아래의 if문은 책을 참고했다. 0이 되는 예외 경우를 잘 따져야 한다.

[답안 예시]

n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort() #정렬 
first = data[n-1]
second = data[n-2]

#가장 큰 수가더해지는 횟수 계산
count = int(m/(k+1)) * k
count += m % (k+1)

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

print(result)

📌

• 위의 코드는 M의 크기가 커졌을 때 시간 초과 판정을 받을 것
• 수열을 이용하여 접근
• 6 6 6 5 / 6 6 6 5, 즉 수열의 길이는 (K+1)
• M을 수열의 길이로 나누면 반복하는 횟수가 나온다. 여기에 K값을 곱해주면 가장 큰 수가 등장하는 횟수가 된다.
• 나누어 떨어지지 않는 경우를 고려하여 나머지만큼 가장 큰 수를 추가 해준다.
• int(M / (k+1)) * k + M % (k+1)

@이것이 코딩 테스트다 with 파이썬