[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 03 그리디 - 실전문제: 큰 수의 법칙

큰 수의 법칙

 

1 _ 문제

'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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보다 작거나 같다.
• 출력 조건
  • 첫째 줄에 동빈이의 큰 수릐 법칙에 따라 더해진 답을 출력한다.
• 입출력 예시

 

---

 

2 _ 문제 해결(고민) 과정

우선, 숫자들을 내림차순으로 정렬해야 할 것 같다.
그리고 가장 큰 숫자가 1개만 있는지, 겹쳐서 2개 이상 있는지 판별해야 할 것 같다.
2개 이상 있는 경우, 그 숫자들을 번갈아서 총 M번 더한다.
1개만 있는 경우, 가장 큰 숫자를 K번 더하고, 두번째로 큰 수를 1번 더하고를 반복해서 총 M번을 더하게 한다.
근데 단순히 더하기만 하면, 계산 과정이 너무 오래 걸릴 것 같다..

K로 M 을 나눠서, 몫만큼 가장 큰 수를 K번 더할까도 고민했다.
나머지를 이용해서 두번 째로 큰 수를 더해주는 방식으로 하는 걸로..
근데 k = 3, M = 9 와 같은 딱 떨어지는 경우 문제가 생긴다. ㅜㅜ

대충 화이트 보드에 끄적끄적 거리다가

찾은 결론은 이거다.
(급하게 적어서 하느라, K 와 M 거꾸로 썼다 ㅎㅎ,,)

 

---

 

3 _ 문제 알고리즘

1. 숫자 내림차순 정렬

2. 가장 큰 숫자의 개수 판별

3. 가장 큰 숫자가 2개 이상으로 중복된 경우
  3 - 1. (가장 큰 수) * M
  3 - 2. 곱한 값이 결론.

4. 가장 큰 숫자가 1개 인 경우
  4 - 1. (K+1)로 M을 나눈다.
  4 - 2. (가장 큰 수) * (몫 * K + 나머지) + (두번째로 큰 수) * 몫
  4 - 3. 계산 결과 값이 결론.

5. 값 출력

 

---

 

4 _ MY CODE

1. 코드

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

data.sort(reverse = True)

first = data[0]
second = data[1]
answer = 0

if(first == second):
  answer = first*m
else: 
  q, r = divmod(m, k+1)
  answer = first*(q*k+r) + second*q

print(answer)

2. 실행 결과

 

---

 

5 _ 교재 답안 코드

1. 첫번째 답안

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 -= 1
    if m == 0:
      break
    result += second
    m -= 1

print(result)

 

2. 두번째 답안

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)

 

 

---

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬