[알고리즘][3][백준_2228][Python3] - 구간 나누기

 

---

문제이해

설명에 앞서 문제에 제시된 M(1≤M≤⌈(N/2)⌉) 에서 

⌈x⌉ 기호는 x보다 작지않은 최소 정수를 의미한다.

 

예를들어 N=10 M=3일때 가능한 조합들중 일부는 다음과같다.

 

 

---

알고리즘 전략

가장 쉽게 떠올릴수 있는 방법은 모든 경우의 수를 전부 해보는것이다.

단 일반 재귀로 작성하면 재귀호출만 해도 말그대로 2^N 만큼의 시간복잡도를 가지므로 중복호출되는 함수는 그 값을 미리 메모이제이션을 해두고 바로 값을 불러오도록 처리를 하면 될것이다.

 

또한 이 문제는 k번째 값을 선택할지말지 고를때 그 앞의 (k-1)개의 선택 현황에 따라 선택지가 달라질수 있다. 즉 앞의 상황과 독립적이지 않다는 것이다. 만약 앞에서 주어진 구간개수를 모두 만들었다면 k이후로는 모든 수를 선택하지 못할수도있다.

 

여기서 앞에서 주어진 구간개수를 모두 만들었어도 만약 직전에 k-1번째의 값을 만약 선택했었다면 k를 넣을수도 있을것이다. 

왜냐하면 k-1까지 선택했다는것은 만약 M=3일때 세번째 구간의 마지막이 k-1번째라는것이기 때문이다.

따라서 k부터 특정 k+i 까지 넣을수도 있다는의미이고 대신 k 이후로 선택하지 않은 숫자가 존재한다면 그 이후로는 전부 선택하지 못할것이다.

 

정리하자면 k번째 인덱스값을 선택할지 말지 정할때 우리가 알아야 할 값들은 

1. 현재 몇개의 구간을 더 만들수 있는지

2. 직전에 값이 선택되었었는지 아닌지

이 두가지이다.

이 변수들이 코드에서는 remain 과 state로 기술되어있다.

 

 

이 문제의 경우 재귀호출을 함에 있어서 필요한 파라미터들은 다음과같다.

arr = 처음에 주어지는 N개의 숫자들을 담고있는 리스트
answer = 메모이제이션을 위한 리스트(초기값은 'no' 이며 해당값이 존재하면 그값을, 존재하지않으면 None 으로 저장된다)
n = N
now = 현재 선택할지말지 결정해야할 index 번호
state = 직전에 숫자를 선택했는지(0) 안했는지(1) 알려주는 변수
remain = 앞으로 만들수있는 구간의 개수

 

메모이제이션을 통한 재귀적 동적계획법에서 중요한 것은 딱 두가지이다.

종료조건과 분류이다.

 

1. 종료조건

만약 N,M이 주어졌을때 0번째 index값부터 시작한다면 
그 값을 선택할지말지 두가지 선택권 있을것이다.

그리고 각각의 경우에따라 1번째 index값을 연속해서 선택할수도
아니면 선택하지 않을수도 있다.

이런식으로 재귀를 통해 다음함수를 실행하다가 n-1번째 인덱스값인 마지막값에 도달하게 되면 현재까지 만들어온 상황이 가능한 상황인지 불가능한 상황인지 판단후 불가능하다면 None을, 가능하다면 마지막 값을 넣을지 말지 적절하게 판단해서 리턴시켜야한다.

2. 분류

이 분류는 위의 빨간 글씨로 쓰인 부분과 연관이 있다. 아래 코드에서는 총 4가지 경우가 나타나있다.
k번째를 선택할지 결정할때

1. k-1 번째를 선택하지않았고 k번째도 선택하지않는 경우
2. k-1 번째를 선택하지않았고 k번째는 선택하는 경우
3. k-1 번째를 선택했고 k번째는 선택하지않는 경우
4. k-1 번째를 선택했고 k번째도 선택하는 경우

사실 1,3번은 호출하는 함수가 같지만 편의상 따로 분류해두었다.
어차피 처음에 if문에서 1,3은 갈라지므로 둘다 한 함수내에서 호출되는 일은 없다.

 

최종 코드는 다음과 같다

 

import sys
sys.setrecursionlimit(10000000) 

def divide(arr,answer,n,now,state,remain): 
    # state : 0 : 직전에 선택하지 않았다. 1 : 직전에 선택했다.
    # remain : 앞으로 만들수있는 구간 개수
    if(now == n-1):
        if(remain == 0):
            if(state == 1 and arr[now] > 0):
                return arr[now]
            else:
                return 0
        elif(remain == 1 and state == 0):
            return arr[now]
        else:
            return None
    if(remain < 0):
        return None

    if(answer[now][remain][state] != 'no'):
        return answer[now][remain][state]
    tmp1 = (-1) * float('inf')
    tmp2 = (-1) * float('inf')
    if(state == 0):
        tmp1 = divide(arr,answer,n,now+1,0,remain)
        tmp2 = divide(arr,answer,n,now+1,1,remain-1)
    else:
        tmp1 = divide(arr,answer,n,now+1,0,remain)
        tmp2 = divide(arr,answer,n,now+1,1,remain)

    if(tmp1 == None or tmp2 == None):
        if(tmp1 == None):
            if(tmp2 == None):
                final = None
            else:
                final = tmp2 + arr[now]
        else:
            final = tmp1
    else:
        final = max(tmp1,tmp2+arr[now])
    answer[now][remain][state] = final
    return final

n, m = input().split(" ")
n = int(n)
m = int(m)

arr = []
answer = [[['no' for col in range(2)] for row in range(m+1)] for depth in range(n+1)]
for i in range(0,n):
    x = int(input(""))
    arr.append(x)

print(divide(arr,answer,n,0,0,m))