[Python] 이코테_그리디_큰 수의 법칙

문제

---

‘큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다.
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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+4+4인 28 이 도출된다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건
• 첫째 줄에 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

 

설계&풀이

---

무지성 구현하면 가능한 문제긴하다. 적어도 이 문제에 한해선 M이 10,000 이하이므로..
하지만 코테는 그렇게 만만하지가 않다. 실제로는 10만이나 100만까지도 나오니, 최적의 로직을 짜야한다.

처음에 짠 코드는 다음과 같다.

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[-1]
sec = data[-2]

# K + 1만큼 길이를 가진 수열이 M // K+1 만큼 반복되고, 이후 M % K+1 만큼의 수열의 인덱스까지 더해준다. (나누어 떨어지지 않을 수 있으니)
sumList = []
for i in range(k):
    sumList.append(first)
sumList.append(sec)

# 이렇게 하면 하나의 수열인 sumList가 완성된다. 이후에 위 조건대로 출력해주면 끝.
result = 0
# 수열을 더한 값들(sum(sumList))이 M // K+1 만큼 더해지니, 다음과 같이 곱해주기
result += sum(sumList) * (m // (k+1))
# 나머지(m%(k+1)) 값의 인덱스만큼 더해주기
result += sum(sumList[:m%(k+1)])
print(result)

이렇게 되면 시간복잡도는 O(k)가 된다. 만약 k가 100만 이상이거나 그랬다면.. 시간초과가 날 것 같다.

풀수는 있지만, 수열에 추가해주는 작업이 필요하기 때문이다.
따라서 우리는 수학적으로 접근해 볼 필요가 있다.

우선 수열을 한 쌍으로 묶은 것 까지는 동일하게 생각해냈다. 다만, 모범답안에서는 큰 수만 더해진 값을 따로 구해주고, 두 번째로 큰 수만 더해진 값을 따로 구해서 for문 없이 풀어냈다.

상세한 풀이는 코드의 주석으로 달아놨으니, 참고하도록 하자.

코드 GIT 주소

---

https://github.com/kkkapuq/AlgorithmStudy/commit/5c75c76274fb14dd14fb98f1c11493232c98b609

이코테_그리디_2_큰 수의 법칙 · kkkapuq/AlgorithmStudy@5c75c76

 

 

코드

---

'''
# 이코테_그리디_실전문제2_큰 수의 법칙
# 난이도 - 하
# 제한시간 - 30분

1. M번 더해서 가장 큰 수를 만들기
2. K번을 초과해서 연속으로 더해질 수는 없음

'''

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[-1]
sec = data[-2]

# ex) k가 3이라면, first를 3번 더한것에 + 1 한게 수열의 길이가 된다.
# 5 8 3이 들어왔다고 가정하면 (8 + 8 + 8 + 5) 이렇게 한쌍이 되는거임
length = k + 1

# 그렇다면 m // k만큼 가장 큰 수가 더해질 것이고, m // k 하고 남은 m % (k+1) 만큼 더 더해주면 된다.
# 예를들어 5 10 3 이 들어왔다면 (8 + 8 + 8 + 5) + (8 + 8 + 8 + 5) + (8 + 8) 이렇게 되는 것이다.
# m // k만큼 가장 큰 수가 나온다
count = (m // length) * k
# m / (k+1)이 나누어 떨어지지 않는다면, m % (k+1) 만큼 가장 큰수를 더 더해준다.
count += m % length

# 결과 출력
result = count * first
# 전체 갯수 m에서 큰 수가 나온만큼인 count를 빼주면 나머지는 두번째로 큰 수의 개수가 된다.
result += (m-count) * sec
print(result)

 

결과

---

 

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡