큰 수의 법칙 [Greedy]

by

(문제) 대수의 법칙: 문제 설명

진행자는 대수의 법칙을 나름의 방식으로 다르게 사용한다. 대수의 법칙에 따르면 서로 다른 수의 집합이 있는 경우 주어진 수는 다음과 같습니다. M회 가장 큰 수를 더하는 규칙입니다. 단, 배열의 특정 인덱스(번호)에 해당하는 번호는 순차적이다. K번더 이상 추가할 수 없는 것이 이 법의 특징입니다.

2, 4, 5, 4, 6의 순서로 배열이 있고 M은 8이고 K는 3이라고 가정합니다. 이 경우 특정 지수의 수는 연속으로 세 번까지 더할 수 있으므로 대수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5, 즉 46입니다.

배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어졌을 때 큰 숫자에 대한 저자의 규칙에 따라 결과를 인쇄합니다.

난이도: ●○○| 해결 시간 30분 | 1초 타임아웃 | 메모리 120MB | 19 국가 기관 코딩 테스트

'추천 관련글,

첫 번째 줄은 자연수 N(2 <= N <= 1,000), M(1 <= M <= 10,000) 및 K(1 <= K <= 10,000)를 제공하며 각 자연수는 공백으로 구분됩니다. .
N개의 자연수는 두 번째 줄에 지정됩니다. 각 자연수는 공백으로 구분됩니다. 그러나 모든 자연수는 1에서 10,000 사이의 숫자로 주어진다.
입력으로 주어진 K는 항상 M보다 작거나 같습니다.

대수의 법칙에 따라 더해진 답이 출력 조건의 첫 줄에 출력된다.

기입 예 출력 예
5 8 3
2 4 5 4 6		 46

1분기 반복하는 가장 빠른 방법은 무엇입니까?
A1. 꼭 필요한 숫자만 가지고 있어야 하나요?

Q2. 그럼 얼마나 많은 숫자가 필요합니까?
A2. M개의 숫자가 필요하며 K번만 반복할 수 있습니다.

3분기 최소 개수를 사용하려면 2개만 사용해야 합니까?
A3. 맞습니다. 그러면 가장 큰 숫자 두 개만 만들면 됩니다. 목록세트 정렬그냥 마지막 두 숫자를 빼서 더하는 것이 좋지 않을까요?

좋아요. 그럼 가자

N,M,K=map(int,input().split()) #N is length of data M is Maximum cycle K is continuty of each data
array=list(map(int,input().split()))

array.sort() # for find max num
res=0 #result

while M:
  for i in range(K):
    if M==0: break
    res+=array(-1) #sum max num
    M-=1 #Check we used turn
  if M==0: break
  res+=array(-2) # when we use all of turn for sum max number, We should use second big number
  M-=1 #Check we used turn

print(res)

<덧셈>

1분기 하지만 지금 생각해보면, 그것들을 추가하기 위해 정말 반복문을 사용해야 할까요?
A1. 오른쪽으로? 어떻게든 숫자를 셀 수 있다면 좋지 않을까요?

Q2. divmod 함수는 아시죠, 파이썬에서 사용하면 어떨까요?
A2. M=10 K=3(M1이 가장 큰 숫자, M2가 두 번째로 큰 숫자)라고 가정합니다.
divmod(10,4)는 return(2,2)이므로 2개의 그룹으로 분할되고 2로 유지됩니다.
→ (M1 M1 M1 M2) – (M1 M1 M1 M2) – M1 M1

3분기 그러면 (M2 * 2 +M1 * (M-2))의 계산식이 나옵니다.
A3. M2에 몫을 더하고 M1에 나머지 수를 더한 것이 결론입니다.

좋아 그럼 구현하자

N,M,K=map(int,input().split()) #N is length of data M is Maximum cycle K is continuty of each data
array=list(map(int,input().split()))

array.sort() # for find max num
res=0 #result

temp=divmod(M,K)(0)
res=array(-2)*temp + array(-1)*(M-temp)

print(res)

루프 명령이 사라진 이후로 시간 복잡도가 크게 향상되었음을 알 수 있습니다.