큰 수의 법칙

 

문제

큰수의 법칙 : N개의 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더해서 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

- 용량 : 128MB, 시간 : 1초

- 2 <= N <= 1000

- 1 <= M <= 10000

- 1 <= K <= 10000

 

입력 예시

5 8 3 (N, M, K)

2 4 5 4 6 (숫자 배열)

 

출력 예시

46

 

 

 

해결

알고리즘 유형

• 구현 알고리즘(게임 형태의 프로그램을 구현하는 알고리즘)
• DFS/BFS 알고리즘(그래프간 연결성을 탐색하는 알고리즘)
• 정렬 알고리즘(조건에 따라 데이터를 정렬하는 알고리즘)
• 이진탐색 알고리즘(그래프에서 특정 데이터를 찾는 알고리즘)
• 다이나믹 알고리즘(순차적인 알고리즘 결과가 서로 영향을 미칠때 결과를 기록하고 처리하는 알고리즘)
• 최단 경로 알고리즘(노드와 노드간 가장 짧은 거리를 찾는 알고리즘)
• 그래프 이론 알고리즘(그래프에서 서로 연결된 노드를 나누는 알고리즘)

이 문제는 내가 아는 유형에 속하지 않으므로 그리디 알고리즘이다.

또한 "가장 큰"이라는 단어가 문제에 들어갔으니 그리디 알고리즘이 더욱 의심된다.

 

 

아이디어

- 데이터를 큰 순서대로 정렬

- result += 가장 작은 인덱스(가장 큰 수) * (M//K*K)

- result += 두번째 인덱스(두번째로 큰 수) * (M%K)

 

 

코드

n, m, k = 5, 8, 3
num = [2, 4, 5, 4, 6]
num.sort(reverse=True)
print(num[0]*(m//k)*k + num[1]*(m%k))

 

 

정당성 체크 및 방식

- 이 문제는 정당성 체크할 필요없이 직관적으로 가장 큰 수를 만들기 위해서는 가장 큰 수들을 더해야한다는 생각이 떠오른다.

- 한 수의 반복은 K번까지이다.

- 가장 큰 수를 K번 더하고 두번째로 큰 수를 한번 더하는 과정을 반복한다.

 

용량 체크

- 고려해야할 부분이 데이터 받는 부분밖에 없는데 이는 딱히 고려할 필요가 없어서 패스

 

시간 체크

- 고려할 부분이 sort 정도인데, python의 sort 시간 복잡도는 NlogN 이다.

- 파이썬은 평균적으로 1초에 5000만번 계산이 가능하다.

- log의 밑이 2이고 최대 1000log1000인데 약 1만번으로 다소 충분하다.