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

그리디의 개념

그리디는 현재 상황에서 지금 당장 좋은 것만 고르는 방법인 탐욕으로 문제를 푸는 알고리즘이다.

거스름돈 예제와 같이 가장 큰 화폐 단위부터 돈을 거슬러 주는 방식을 선택하는 것이 그리디 방식이다

큰 수의 법칙

아이디어 : ( 가장 큰 수를 최대 연속횟수만큼 더해주고 + 그 다음을 큰 수를 한번 더해주기 ) 이 과정을  수가 더해지는 횟수만큼 반복해주면 된다

 

구현 

가장 큰 수 구하기 : 인덱스가 다르면 수가 같아도 다른 수 취급을 하기 때문에 list를 내림차순으로 정렬한 후 [0]번째 수를 구하면 된다

두 번째로 큰 수 구하기  : 같은 이유로 [1]번째 수를 구하면 된다.

 

반복 횟수 : 반복 회수는 m번 만큼 반복되어야한다.

 

반복 횟수를 어떻게 m번만큼 할 수 있을까?

count 변수를 활용

 

순수하게 count 변수를 활용해서 m과 같아지면 반복문을 탈출하도록 했다.

 

내 코드

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

list = list(map(int, input().split()))
list.sort(reverse=True)

max = list[0]
second = list[1]
sum = 0
count=0

for _ in range(m):
  for _ in range(k):
    sum +=max
    count += 1
    if count == m:
      break
  sum += second
  count +=1
  if count ==m:
    break
print(sum)

 

 

💡새로운 아이디어 

더할 때 마다 m값을 1만큼 감소시켜주고  m이 0이 되면 반복문이 종료되도록 설정

 

while True:
  for _ in range(k):
    if count == m:
      break
    sum +=max
    count += 1
  sum += second
  count +=1
  if count ==m:
    break
print(sum)

 

<< 차이 >>

 

for문을 m만큼 반복하는 것 <-> while True 문으로 변경

m이 되면 반복문 종료 <-> m == 0 이라면 반복문 종료

 

🌟배운점

1. 반복문 횟수를 어떻게 설정해야할지 고민이었는데 While True 문을 설정하고 반복문 종료 조건을 설정하면 되는 것이었다! 

2. count 변수를 만들어서 count 변수를 1씩 증가시켜 줄수도 있는데 m을 1씩 감소시켜주는 방식으로도 사용할 수 있었다.

 

M이 더 커진다면?

현재는 M이 최대 10,000으로 정해져있다.

그러나 만약 M이 100억이상으로 커질 경우에는 현재와 같은 반복문 연산을 이용할 경우 시간 초과가 발생한다.

 

따라서 반복문을 사용하지 않는 로직을 구현해보자!

 

2 4 5 4 6 에서

가장 큰 수는 6

두번째로 큰 수는 5 

 

반복되는 수열 : [6, 6, 6, 5]

반복되는 수열의 길이 : k+1 인 4이다

수열의 반복 횟수 : m // (k+1) 

나누어떨어지지 않는 경우 :  나머지 만큼 큰 수가 추가로 더해진다.

 

즉 가장 큰 수가 더해지는  횟수는 

= m//(k+1)*k + m % (k+1)

이다. 

 

이제 두번째로 큰 수가 더해지는 횟수를 구할 수 있다.

m - 가장 큰 수가 더해지는  횟수 를 해주면 구할 수 있다.

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

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

# 가장 큰 수가 더해지는 횟수 계산
count = 0
count += m//(k+1) * k +( m %(k+1))

sum=0
sum += count *first
sum +=( m-count) *second

print(sum)