https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/
MinMaxDivision coding task - Learn to Code - Codility
Divide array A into K blocks and minimize the largest sum of any block.
app.codility.com
You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.
You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.
The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.
The large sum is the maximal sum of any block.
For example, you are given integers K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2
The array can be divided, for example, into the following blocks:
- [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
- [2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
- [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
- [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.
Write a function:
def solution(K, M, A)
that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.
For example, given K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2
the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and K are integers within the range [1..100,000];
- M is an integer within the range [0..10,000];
- each element of array A is an integer within the range [0..M].
또 좀 어려워 보이는 녀석이다.
문제 읽는데, 이건 머리로 감도 안 잡히는 수준이다 에효..
어렵다 어려워.. 애증의 Recursive 짜식
1. Python
아 recursive는 봐도 모르겄다 이제..
def is_valid_block_size(A, max_block_sum, K):
current_sum = 0
block_count = 1 # 최소 하나의 블록은 있어야 함
for element in A:
if current_sum + element > max_block_sum:
block_count += 1 # 새로운 블록 시작
current_sum = element
if block_count > K:
return False
else:
current_sum += element
return True
def solution(K, M, A):
# 이진 탐색의 범위: 가장 큰 값에서 전체 합까지
lower_bound = max(A) # 최소값은 배열에서 가장 큰 값
upper_bound = sum(A) # 최대값은 배열의 모든 값의 합
result = upper_bound
while lower_bound <= upper_bound:
mid = (lower_bound + upper_bound) // 2
if is_valid_block_size(A, mid, K):
result = mid # 가능한 해를 저장
upper_bound = mid - 1 # 더 작은 블록 크기를 찾기 위해 상한 감소
else:
lower_bound = mid + 1 # 더 큰 블록 크기가 필요하므로 하한 증가
return result
Binary Search로 푸는 방법도 이건데,
꼭 Recursive가 divde and conquer은 아니니까 참고해야겠다.
시간은 .. O(N*log(N+M)) 이다.
C랑 C++은 잘 모르겠따.
코드에 대한 설명은 다음과 같다..
|
Python 코드를 단계별로 자세히 설명해드리겠습니다.
Detailed Explanation of Minimum Large Sum Solution
Click to open code
CopyRetry
B
근데 max_sum을 넘지 않는 조건을 만족해도, 그 값을 정확히 만들 수 있는 block이 있는지는 모르는거 아니야? 그런데 result에다가 mid 값을 저장해도 되나
Edit
좋은 질문입니다! 이 부분이 처음에는 헷갈릴 수 있는데, 다음과 같은 이유로 문제가 없습니다:
max_sum = 7로 시도할 때:
이렇게 이진 탐색으로 찾은 값이 실제로 가능한 최소값이 됩니다. 각 블록의 합이 정확히 그 값일 필요는 없고, 그 값 이하이기만 하면 됩니다. |
def check_division_possible(A, K, max_sum):
"""
배열 A를 K개 이하의 블록으로 나눌 수 있는지 확인하는 함수
각 블록의 합이 max_sum을 넘지 않아야 함
예: A=[2,1,5,1,2,2,2], K=3, max_sum=6인 경우
[2,1] [5,1] [2,2,2] -> 가능 (각 블록 합: 3,6,6)
"""
blocks = 1 # 현재 만들어진 블록 수
current_sum = 0 # 현재 블록의 합
for num in A:
# 단일 숫자가 max_sum보다 크면 불가능
if num > max_sum:
return False
# 현재 블록에 이 숫자를 더했을 때 max_sum을 초과하면
if current_sum + num > max_sum:
blocks += 1 # 새 블록 시작
current_sum = num # 새 블록의 첫 숫자
else:
current_sum += num # 현재 블록에 숫자 추가
# 필요한 블록 수가 K를 초과하면 실패
if blocks > K:
return False
return True # K개 이하의 블록으로 나누기 성공
def solution(K, M, A):
if K == 1: # 블록이 1개면 전체 합이 답
return sum(A)
if K >= len(A): # 블록이 배열 길이보다 크거나 같으면
return max(A) # 가장 큰 원소가 답
# 이진 탐색의 범위 설정
left = max(A) # 가능한 최소값 (배열의 최댓값)
right = sum(A) # 가능한 최대값 (배열의 총합)
result = right # 현재까지의 최적해
# 이진 탐색 수행
while left <= right:
mid = (left + right) // 2 # 중간값을 max_sum 후보로 시도
# 현재 mid값으로 K개 이하 블록 나누기가 가능한지 확인
if check_division_possible(A, K, mid):
result = mid # 가능하다면 일단 저장
right = mid - 1 # 더 작은 값도 가능한지 시도
else:
left = mid + 1 # 불가능하다면 더 큰 값 시도
return result
# 예시:
A = [2, 1, 5, 1, 2, 2, 2]
K = 3
M = 5
# 이진 탐색 과정 예시:
# 1. left=5, right=15, mid=10 -> 가능 -> result=10, right=9
# 2. left=5, right=9, mid=7 -> 가능 -> result=7, right=6
# 3. left=5, right=6, mid=5 -> 불가능 -> left=6
# 4. left=6, right=6, mid=6 -> 가능 -> result=6, right=5
# 5. left=6, right=5 -> 종료
# 최종 결과: 6
정말 어렵다..
즉 일단 Array가 있으면, 그 놈으로 만들 수 있는 block의 최대/최소를 설정하고,
얘를 right/left로 설정한다음에 mid 값을 기준으로 K개의 block을 나눴을 때 모든 block이 mid값 이하가 될 수 있게 만들 수 있는지를 체크한다.
얘를 들어 mid = 8 OK, mid =7 OK, mid = 6 Not OK 이면, mid가 7인 경우가 block의 SUM이 제일 낮은 케이스다.
처음에 설명을 들었을 땐, mid = 8에서 OK가 나와도 mid 7, 6 에서도 OK가 뜰 수 있는 거 아닌가. .했는데, 어차피 while문 돌면서 Not OK 가 뜰 때까지 mid 값을 다 넣어보기 때문에 상관이 없는 걱정거리였다.
참말로 어려웠던 문제..
다시 풀이 보지 않고, No - Base로 한 번 풀어봐야겄다.
- Retry
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def sol_help(K,A,mid):
block = 1
curr_sum = 0
for x in A:
if x > mid :
return False
if curr_sum + x > mid :
block +=1
curr_sum = x
else :
curr_sum += x
if block > K : return False
return True
def solution(K, M, A):
# Implement your solution here
left = max(A)
right = sum(A)
if K==1 : return right
if K>=len(A) : return left
ans = 0
while left <= right:
mid = (left+right)//2
if sol_help(K,A,mid) :
ans = mid
right = mid-1
else : left = mid + 1
return ans
죽겄다 진짜!!
'Coding_Practice' 카테고리의 다른 글
| Maximum Swap[Math,Greedy] (2) | 2024.10.17 |
|---|---|
| Search a 2D Matrix II[M,Array,Binary Search,Divide and Conquer,Matrix] (0) | 2024.10.16 |
| MaxProductOfThree (0) | 2024.10.16 |
| Quick_Sort 문제 풀기(Divide and conquer) (1) | 2024.10.16 |
| Pascal's Triangle II[E,Array,Dynamic Programming] (1) | 2024.10.14 |