728x90
반응형
그리디 문제 중 큰 수의 법칙 문제를 풀어보자.
문제
큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
입력 조건
N : 배열의 크기
M : 숫자가 더해지는 횟수
K : 연속 가능한 수의 갯수
출력
첫째 줄에 입력한 값에 따라 다르다.
예
배열 2,4,5,4,6 이 있을 때 M=8, K=3 이면 6+6+6+5+6+6+6+5 = 46 이 된다.
배열 3,4,3,4,3 이 있을 때 M=7, K=2 이면 4+4+4+4+4+4+4 = 28 이 된다.
나의 풀이
# 큰 수의 법칙
# 다향한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
# 문제 (예를 들어 설명)
# 2,4,5,4,6 의 배열이 있을 때 M(더하는 횟수)이 8이고, K(한 숫자가 연속해서 더해질 수 있는 갯수)가 3 일 때 합이 가장 큰 경우는
# 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 이 된다. (4 같은 경우는 2개 존재하므로 다른 숫자로 취급한다.) 최대가 되는 수를 구하라.
N,M,K = map(int,input().split())
data = list(map(int,input().split())) # 리스트 입력 받는 방법
data.sort() # 정렬
sum=0
count = 1
for i in range(0,M):
if count%K!=0:
sum += data[N-1]
else:
sum += data[N-2]
count +=1
print(sum)나는 배열을 정렬시켜놓고 끝값과 그 앞의 값만 구하고 count % K 의 값에 따라 6을 더할지 5를 더할지 반복하였다.
전형적인 초보자의 방법이란다... 뜨끔
책 풀이
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)이 정답 보면서 느낀게 생각이 반복문에 박혀있다 보니까 저런 생각이 떠오르지 않았다는고 다른 문제 많이 풀어봐야겠구나라고 생각했다.
위 정답은 간단하다.
{6+6+6+5} 의 수열이 반복되는 상황이고
수열의 길이는 K+1 (여기선 4) 이면
수열의 갯수는 M/(K+1)가 되며
가장 큰 수가 등장하는 수는 수열의 갯수( M/(K+1) ) * 연속 수(K) 로 M/(K+1) * K 가 되고
나누어 떨어지지 않는 경우에는 나머지 만큼 가장 큰 수를 추가로 더해줘야 하므로
int ( M / (K+1) )* K + M % (K+1) 이 된다.
728x90
반응형
