[코딩 테스트] 5일차.

결정 알고리즘

이분탐색>
1 2 3 4 5 6 7 8 9 가 주어졌을때 M의 갯수로 범위를 나누었을 때 최대가 될 수 있는 합은 ?
M = 3일때, (1, 2, 3, 4, 5) (6, 7), (8, 9)로 쪼갰을 때 최대 합의 값이 될 수 있다. => 17

그럼 어떻게 해야 M개의 조합으로 나눌 수 있을까.
Combination으로 itertools 라이브러리는(삼성코테에서 막힘).

    for i in MV:
        if sum + i > mid:
            cnt += 1
            sum = i
        else:
            sum += i

다음과 같은 코드를 보면, 갯수를 나눌 수 있다.
(1, 2, 3, 4, 5)까지 하면 mid = (s + e) //2 의 값보다 클 때
sum을 다음 6으로 초기화한다. 동시에 cnt 1만큼 증가 그리고 같은 방식으로 진행해 나간다. (6, 7) 8까지 하면 sum 초과하므로 1~5/6~7/8~9 로 총 3개로 쪼개어진다.

while True:
	...
    if cnt <= M:
        res = mid
        e = mid - 1
    else:
        s = mid + 1
    if s > e:
        break

이렇게 쪼개어진 집합의 갯수를 구해 M보다 작거나 같을 경우에는 mid 값을 낮추어(e = mid - 1) 최대합의 값을 구해야한다. 조건을 만족했으므로 일단 res에 결과값을 넣고, 최대를 구하기 위해 s > e가 될 떄까지 계속적으로 반복한다.

K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다.

라면 이중반복문으로 로직을 짤 경우, 시간초과도 1,000,000,000(1초)를 넘는다.
결정알고리즘(범위 안에 답이 있음을 인지하고 있음)으로 이분탐색으로 문제 접근을 한다.
(어떻게 탈출? start > end 일경우 종료.)

자료구조 파트를 넘어 이제 조금씩 알고리즘으로 넘어왔다. 분발해야겠다.