[그리디] 큰 수의 법칙

[문제]

 

- 배열의 갯수는 N 이다.

- 주어진 배열에서 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 = 28 이다.

 

[아이디어]

 

- 배열에서 첫번째로 큰수를 찾고, 이걸 최대횟수 (K) 만큼 더해준다.

- 배열에서 두번째로 큰수를 찾고, 이걸 최소횟수 (1) 만큼 더해준다.

- 그다음 첫번째로 큰수를 다시 (K) 만큼 더해준다. 

 

n = 5
m = 8
k = 3
data = [2, 4, 5, 4, 6]
print(data)

data.sort()
print(data)

first = data[n-1]
second = data[n-2]    # 두번째로 큰수는 같더라도 second로 저장
result = 0

while True:
  for i in range(k):  # 최대실행은 k
    if m==0:          # 합산횟수가 0이되면 종료
      break
    result += first   # 첫번째로 큰수를 더해줌 
    m -= 1            # 합산횟수 -1
      
                      # second 합은 1회만 이루어진다.
  if m==0:            # 합산횟수가 0이되면 종료
    break
  result += second    # 두번째로 큰수를 더해줌
  m -= 1              # 합산횟수 -1

print(result)

[풀이]

 

- 주어진 data에서 첫번째로 큰수와 두번째로 큰수를 정한다.

- 오름차순으로 sort를하고 뒤에서부터 두개의 데이터를 뽑으면, 저절로 첫번째/두번째 큰수가 정해진다.

- 가장 큰수가 2개라 하더라도, 위와같이 두개로 뽑힌다.

- 첫번째로 큰수는 K번 반복을 하여 result에 더해준다.

- 두번째로 큰수는 1번 result에 더해준다.

- 덧셈이 0이 되면 (m==0) 반복문을 빠져나온다.

 

[결과]

- 문제는 풀렸지만, 한가지 문제점이 발생한다.

 

import time
start_time = time.time()
##

n = 5
m = 10000000
k = 3
data = [2, 4, 5, 4, 6]
print(data)

.
.
.
.

##
end_time = time.time()
print ("TIME : ", end_time - start_time)

위와같이 m을 10000000 (1천만) 으로 설정하고 시간을 측정해보니, time 이 약 11초가 걸리는것이 확인되었다.

20000000 (2천만) 으로 설정하니 약 22초가 소모되었다. 즉, 문제에서 만약 m 으로 큰숫자를 잡아버린다면 위 문제는 time out 이 발생해버린다.

 

[아이디어]

- 숫자는 아래와같은 형식으로 더해진다. 

- [ 2, 4, 5, 4, 6], M=8, K=3 이라면, 6+6+6+5 + 6+6+6+5 = 46 이다.

- M이 계속해서 커진다고 가정해보면, 아래와같은 수열이 만들어진다.

- 6665 6665 6665 6665 ....... 6665 6665 66 

- 6665가 특정횟수 반복되고, 나머지가 더해지게 된다.

- '6665' 라는 '반복구' 라는것에서 아이디어를 뽑아본다.

- 반복구에서 큰수(6)는 k(3) 만큼 횟수가 더해지고, 반복구 자체는 m / (k+1) 만큼 반복된다. 

- 따라서, m/(k+1) * k 만큼 first 가 더해진다.

- 나머지(66) 에서는 m % (k+1) 만큼 큰수가 더해졌다.

 

- 두번째로 큰수는 반복구에서 (k+1) - k 만큼 반복된다. 즉 [m/(k+1) * {(k+1) - k}] = m/(k+1) * 1 만큼 반복된다.

- 두번째로 큰수는 첫번째로 큰수처럼 나머지를 생각할필요가 없다. 두번째로 큰수는 반복구에서 1번만 나올수 있으며, 1번이 나왔다면 이는 반복구 자체가 되므로 의미가 없다.

 

import time
start_time = time.time()
##

n = 5
m = 10000000
k = 3
data = [2, 4, 5, 4, 6]
print(data)
data.sort()
print(data)
first = data[n-1]
second = data[n-2]    # 두번째로 큰수는 같더라도 second로 저장
result = 0

# int 가 없다면 소숫점으로 값이 나온다
first_count = int(m/(k+1))*k + m%(k+1)
second_count = int(m/(k+1))*1

result = first_count*first + second_count*second
print(first_count, second_count)
print(result)

##
end_time = time.time()
print ("TIME : ", end_time - start_time)

 

[결과]

- 단순한 연산으로 결과가 나오다보니, 이전코드에서는 m이 1천만일때 11초가 걸렸는데, 위 코드로는 시간이 거의 안걸리는 식으로 1번의 연산으로 결과가 나오게되었다...;