그리디 알고리즘 (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 파이썬
Programmer & Media