[알고리즘][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))