당신은 온라인 게임을 운영하고 있습니다. 같은 시간대에 게임을 이용하는 사람이 m명 늘어날 때마다 서버 1대가 추가로 필요합니다. 어느 시간대의 이용자가 m명 미만이라면, 서버 증설이 필요하지 않습니다. 어느 시간대의 이용자가 n x m명 이상 (n + 1) x m명 미만이라면 최소 n대의 증설된 서버가 운영 중이어야 합니다. 한 번 증설한 서버는 k시간 동안 운영하고 그 이후에는 반납합니다. 예를 들어, k = 5 일 때 10시에 증설한 서버는 10 ~ 15시에만 운영됩니다.
하루 동안 모든 게임 이용자가 게임을 하기 위해 서버를 최소 몇 번 증설해야 하는지 알고 싶습니다. 같은 시간대에 서버를 x대 증설했다면 해당 시간대의 증설 횟수는 x회입니다.
players의 길이 = 24 0 ≤ players의 원소 ≤ 1,000 players[i]는 i시 ~ i+1시 사이의 게임 이용자의 수를 나타냅니다. 1 ≤ m ≤ 1,000 1 ≤ k ≤ 24
그리디(Greedy) + 누적 관리 기법
그리디 알고리즘은 현재 시점에서 최적의 선택을 반복하여 전체 최적해를 구하는 방식입니다. 즉, “미래를 고려하지 않고 지금 당장 가장 좋은 선택을 한다”는 전략을 사용합니다.
🎯 언제 사용할까?
그리디 알고리즘이 최적해를 보장하려면 다음 두 가지 조건을 만족해야 합니다.
1️⃣ 탐욕적 선택 속성 (Greedy Choice Property)
현재 선택이 이후의 선택에 영향을 주지 않고 독립적이어야 함. 즉, 각 단계에서의 최적 선택이 전체 문제의 최적해를 만들 수 있어야 함.
2️⃣ 최적 부분 구조 (Optimal Substructure)
문제를 부분 문제로 쪼갰을 때, 각 부분 문제의 최적해가 전체 문제의 최적해를 만들 수 있어야 함. 즉, “부분 최적해”를 조합하면 “전체 최적해”가 되어야 함.
사용 연어: JavaScript
테스트 1 〉 통과 (4.15ms, 33.6MB)
테스트 2 〉 통과 (3.06ms, 33.5MB)
테스트 3 〉 통과 (9.32ms, 33.6MB)
테스트 4 〉 통과 (2.53ms, 33.8MB)
테스트 5 〉 통과 (3.90ms, 33.5MB)
테스트 6 〉 통과 (3.72ms, 33.6MB)
테스트 7 〉 통과 (4.05ms, 33.7MB)
테스트 8 〉 통과 (2.85ms, 33.6MB)
테스트 9 〉 통과 (3.38ms, 33.7MB)
테스트 10 〉 통과 (3.22ms, 33.7MB)
테스트 11 〉 통과 (2.13ms, 33.6MB)
테스트 12 〉 통과 (2.18ms, 33.7MB)
테스트 13 〉 통과 (3.26ms, 33.6MB)
테스트 14 〉 통과 (2.85ms, 33.6MB)
테스트 15 〉 통과 (3.01ms, 33.7MB)
테스트 16 〉 통과 (2.75ms, 33.6MB)
테스트 17 〉 통과 (0.07ms, 33.5MB)
테스트 18 〉 통과 (0.08ms, 33.6MB)
테스트 19 〉 통과 (3.06ms, 33.6MB)
테스트 20 〉 통과 (3.15ms, 33.6MB)
테스트 21 〉 통과 (5.10ms, 33.7MB)
테스트 22 〉 통과 (2.74ms, 33.7MB)
테스트 23 〉 통과 (0.08ms, 33.5MB)
테스트 24 〉 통과 (3.34ms, 33.6MB)
테스트 25 〉 통과 (0.07ms, 33.5MB)
테스트 26 〉 통과 (4.27ms, 33.6MB)
테스트 27 〉 통과 (2.43ms, 33.5MB)
테스트 28 〉 통과 (2.17ms, 33.6MB)
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.