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

문제

큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 

단, 1) 배열의 특정한 인덱스에 해당하는 수가 K번을 초과하여 더해질 수 없는 것이 특징

2) 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주

 

ex)

2,4,5,4,6의 배열 , M = 8, K =3

큰 수의 법칙에 따라 6 + 6+ 6 + 5 + 6 + 6+ 6+ 5 = 46 

 

입력 조건

• 첫째줄에 N(2 <N <1,000), M(1, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다, 각 자연수는 공백으로 구분한다, 단, 각각의 자연수는 1 이상 10,000 이 하의 수로 주어진다.
• 입력으로 주어자는 K는 항상 M보다 작거나 같다. 

5 8 3 
2 4 5 4 6

출력 조건

• 첫째 줄의 큰 수의 법칙에 따라 더해진 답을 출력한다.

46

 

 

내가 푼 답안

N, M, K = map(int, input().split())
data = list(map(int, input().split()))

#리스트 내 가장 큰 수의 인덱스 찾기
#큰 수가 리스트 내 중복될 수 있기 때문에 인덱스 리스트 생성
m = max(data)
index = [i for i, val in enumerate(data) if val==m]

#인덱스 길이가 1이라면 두 번째로 큰 수 찾기
if len(index) == 1 :
  first = max(data)
  data.remove(first)
  second = max(data)
else:
  first = data[index[0]]
  second = data[index[1]]

answer = 0
while True:
  if M == 0 :
    break
  #가장 큰 수 k번 더하기
  for k in range(K):
    if M == 0 :
      break
    if M == K : #m이 k와 같다면 큰 수 k번만 더하면 됨
      answer += first  
    else :
      answer += first
      M -= 1
  if M == 0 :
    break
  answer += second
  M -= 1

print(answer)

출력 결과 58로 틀린 답안이 나왔다.

 

⭐️  틀린 이유

if M== K : answer += first 문에서 M을 감소시키지 않았기 때문에 M의 숫자와 상관없이 큰 수 K번을 더해버리게 된다.

따라서 답보다 더 큰 출력결과가 나와버렸다.

전체적으로 코드도 길고 복잡하다

 

정답 코드

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

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

answer = 0
while True:
  for i in range(k):
    if m == 0 :
      break 
    answer += first
    m -=1
  if m == 0:
    break 
  answer += second
  m -=1

print(answer)

 

느낀점

답안코드와 내 코드를 비교해보면서 내 코드는 왜이렇게 길었을까? 고민해봤다. 

첫번째,

리스트의 최대값 인덱스를 고려할 필요없이 큰 수랑 두 번째로 큰 수만 뽑아내면 됐다. 

이 문제의 핵심 풀이는 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번만 더하는 연산을 반복하면 되는거니까..!

그리고 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제되는 경향이 있다고!!

리스트 정렬 sort() 메서드를 잘 사용해봐야겠다 

두번째,

K는 M보다 항상 작거나 같다고 해서 같은 경우를 조건절로 만들었는데, 이 또한 고려할 필요가 없었다. 

M을 감소시키면서 0이 될 때까지 핵심 연산을 반복하면 되기 때문이다.

만약 K == M 조건절을 사용한다면 M을 감소시키는 연산도 추가해줘야 오답이 나지 않는다는 점도 알게되었다.

알고리즘 쉽지 않구나.. 매일 꾸준히 연습하자!