안겹치게 구간을 나누는 다이나믹 프로그래밍 테크닉
문제1.
n개의 오렌지가 1번부터 n번까지 순서대로 있는데, 순서대로 앞에서부터 상자에 나눠서 넣는다
이때 한 상자에 넣는 오렌지는 번호가 연속해야한다
한 상자당 최대 m개까지 오렌지를 넣을 수 있다
이때 상자를 포장하는 비용은 K + s*(a-b)로 s는 상자에 넣는 오렌지의 개수이고 a는 오렌지 크기의 최댓값, b는 최솟값이다
이때 모든 오렌지를 포함하는 비용의 최솟값은?
-------------------------------------------------------------------------------------------------------------------------
dp[i] = i번째 오렌지까지 포장하는데 드는 비용의 최솟값
i = 0인 경우 dp[0]는 얼마인가?
1개만 상자에 넣기 때문에 s = 1, a = A[0], b = A[0]이므로 비용은 K이다
즉 dp[0] = K
i = 1,2,3...,n-1에 대하여 j = 0,1,2,....번째부터 i번째까지 오렌지를 현재 상자에 넣는다고 생각해보자
i부터 역순으로 순회해서 상자에는 최대 m개를 넣을 수 있으므로, i-m+1까지
즉 j = i-m+1일 경우 i-m+1 ~ i번 오렌지를 현재 상자에 넣는다고 생각하는 것이다
j = i-m+2일 경우 i-m+2 ~ i번 오렌지를 상자에 넣고
j = i-m+3일 경우 i-m+3 ~ i번 오렌지를 상자에 넣고
....
j = i일 경우 i ~ i번 오렌지를 상자에 넣는다
이 구간에서 최댓값과 최솟값을 찾아야하므로 max = 0, min = INF로 초기화하고
j~i번 오렌지를 상자에 넣으므로 오렌지의 개수는 i-j+1개
돌면서 j ~ i번 구간 최댓값 최솟값이 max,min으로 구해지므로 j~i번 오렌지를 상자에 넣는 비용은 k + (i-j+1)(max-min)
j~i번 오렌지를 새로운 현재 상자에 넣으므로 지금까지 상자에 포장한 비용은? dp[j-1]
즉, dp[i] = dp[j-1] + k + (i-j+1)(max-min)
j = 0인 경우에는 지금까지 상자에 넣은 오렌지가 없으므로 dp[i] = k + (i-j+1)(max-min)
from sys import stdin
n,m,k = map(int,stdin.readline().split())
A = []
for _ in range(n):
a = int(stdin.readline())
A.append(a)
INF = 10**18
dp = [INF]*n
dp[0] = k
for i in range(1,n):
Max = 0
Min = INF
for j in range(i,max(0,i-m+1)-1,-1):
if Max < A[j]:
Max = A[j]
if Min > A[j]:
Min = A[j]
cost = k + (i - j + 1)*(Max-Min)
if j >= 1 and dp[j-1] + cost < dp[i]:
dp[i] = dp[j-1] + cost
elif j == 0 and cost < dp[i]:
dp[i] = cost
print(dp[n-1])
핵심은 j를 정방향으로 돌면 틀린다
역순으로 돌아야함
왜냐하면 정방향으로 순회하면 j ~ i번까지의 오렌지에서 최댓값 최솟값이 제대로 안구해지기 때문이다
A = [3,10,13,10,19,9,12,16]이라고 하자
i = 5인 경우 m = 4일때 j ~ i번 구간의 최대 최소를 찾아본다
5 ~ 5번 구간은 9,9
4 ~ 5번 구간은 19,9
3 ~ 5번 구간은 19,9
2 ~ 5번 구간은 19,9
A = [3,10,13,10,19,9,12,16]
n = len(A)
INF = 10**18
m = 4
i = 5
Max = 0
Min = INF
for j in range(i,max(0,i-m+1)-1,-1):
if Max < A[j]:
Max = A[j]
if Min > A[j]:
Min = A[j]
print(f'{j} ~ {i} : {Max},{Min}')
5 ~ 5 : 9,9
4 ~ 5 : 19,9
3 ~ 5 : 19,9
2 ~ 5 : 19,9
근데 정방향으로 순회하면 이상하게 구해진다
당연한게 2 ~ 5번 최대 최소를 구하기 위해 2 ~ 5번을 전부 봐야하는데 2번만 보고 최대 최소를 구해버리니까
A = [3,10,13,10,19,9,12,16]
n = len(A)
INF = 10**18
m = 4
i = 5
Max = 0
Min = INF
for j in range(max(0,i-m+1),i+1):
if Max < A[j]:
Max = A[j]
if Min > A[j]:
Min = A[j]
print(f'{j} ~ {i} : {Max},{Min}')
2 ~ 5 : 13,13
3 ~ 5 : 13,10
4 ~ 5 : 19,10
5 ~ 5 : 19,9
---------------------------------------------------------------------------------------------------------------------------------------------------------------
문제2.
n명의 학생이 있는데 각각의 조에서 구성된 가장 높은 학생의 점수와 가장 점수가 낮은 학생의 점수 차이의 합이 최대가 되도록 구성한다
조의 개수는 상관이 없고 1명으로 구성된 조는 최댓값과 최솟값의 차이는 0이 된다
이때 점수 차이 합의 최댓값을 찾는다면?
-----------------------------------------------------------------------------------------------------------------
위와 똑같은 테크닉으로 구현하면 된다
dp[i] = i번째 학생까지 봤을 때 전체 조가 짜여진 정도의 최댓값
dp[0] = 0, 1명으로 구성된 조는 최대 최소가 동일하므로
i = 1,2,3,...,n-1에 대하여...
j = i,i-1,i-2,..,0으로 역으로 순회하여 j번부터 i번까지 학생을 하나의 조로 구성한다
j~i구간에서 최대와 최소를 알아야하므로 max_s, min_s를 적당히 초기화하고 최대 최소 차이를 구한다
j = 0인 경우 0번에서 i번까지 학생들이 하나의 조가 되므로, dp[i] = max(dp[i],max_s - min_s)
j >= 1인 경우는 j ~ i번까지 학생들이 하나의 조가 되고, 이전까지 구성된 합은 dp[j-1]이므로
dp[i] = max(dp[i], dp[j-1] + max_s - min_s)
n = int(input())
A = list(map(int,input().split()))
#dp[i] = i번째 학생까지 봤을때 전체 짜여진 정도
dp = [0]*n
for i in range(1,n):
max_s = A[i]
min_s = A[i]
#j부터 i까지 한 팀으로 묶었을때
#dp[j-1] + max_s - min_s
for j in range(i,-1,-1):
if max_s < A[j]:
max_s = A[j]
if min_s > A[j]:
min_s = A[j]
if j == 0:
if dp[i] < max_s - min_s:
dp[i] = max_s - min_s
else:
if dp[i] < dp[j-1] + max_s - min_s:
dp[i] = dp[j-1] + max_s - min_s
print(dp[n-1])
문제3.
n개의 수에서 m개의 구간을 선택하는데, 각 구간은 겹쳐있으면 안되고 인접해서도 안된다
정확히 m개의 구간이 있어야한다
각 구간은 1개 이상의 연속된 수들로 이루어진다
이때 각 구간에 속한 수들의 총 합이 최대가 되도록 구간을 나눈다
---------------------------------------------------------------------------------------------------------------------------
인접하면 안된다는 조건때문에 좀 더 어렵다
dp[i][j] = i번째까지 썼을때 j번째 구간까지 총 합의 최댓값
그러면 0번 원소는 1번 구간만 있으므로 dp[0][1] = A[0]
i = 1,2,3,...,n-1에 대하여 j = 1,2,..,m번째 조에 대해
j번째 조에 k번째부터 i번째 원소를 넣는다고 하자
위에서 사용한 테크닉으로 k~i 구간의 원소들 총 합을 알아야하므로
k = i,i-1,i-2,...,0까지 역으로 순회해서 처음에 s = 0으로 초기화해서 하나씩 더해나가면...
#dp[i][j] = i번째까지 썼을때 j번째 조까지 총 합의 최댓값
dp = [[-3276811]*(m+1) for _ in range(n)]
dp[0][1] = A[0]
for i in range(1,n):
for j in range(1,m+1):
max_s = -3276811
s = 0
#j번째 조에 k번째부터 i번째까지 쓸때
for k in range(i,-1,-1):
s += A[k]
현재 구간이 하나만 있는 경우 j = 1인 경우는 k~i번째 원소 합을 그대로
dp[i][j] = max(dp[i][j], max_s)
반면 구간이 2개 이상 있는 경우, j >= 2인 경우는 각 구간이 인접하지 않아야하므로
k번째부터 i번째까지 원소를 j번째 구간에 쓴다면...
그 이전까지 구간은 0 ~ k-2번째 원소까지 j-1개의 구간에 넣고 k-1은 건너뛰고 k~i번째 원소를 j번째 구간에 넣는 것
#dp[i][j] = i번째까지 썼을때 j번째 조까지 총 합의 최댓값
dp = [[-3276811]*(m+1) for _ in range(n)]
dp[0][1] = A[0]
for i in range(1,n):
for j in range(1,m+1):
max_s = -3276811
s = 0
dp[i][j] = dp[i-1][j]
#j번째 조에 k번째부터 i번째까지 쓸때
for k in range(i,-1,-1):
s += A[k]
if max_s < s:
max_s = s
if j == 1:
dp[i][j] = max(dp[i][j], max_s)
else:
if k >= 2:
dp[i][j] = max(dp[i][j], dp[k-2][j-1] + max_s)
여기서 i번째 원소는 구간에 포함되지 않아도 되므로
dp[i][j] = dp[i-1][j]로 이전까지 계산해놓은 값을 초기화해줘야한다
합이 음수일 수 있기 때문에 최초 초기값은 음수로 초기화해야
n,m = map(int,input().split())
A = []
for _ in range(n):
a = int(input())
A.append(a)
#dp[i][j] = i번째까지 썼을때 j번째 조까지 총 합의 최댓값
dp = [[-3276811]*(m+1) for _ in range(n)]
dp[0][1] = A[0]
for i in range(1,n):
for j in range(1,m+1):
max_s = -3276811
s = 0
dp[i][j] = dp[i-1][j]
#j번째 조에 k번째부터 i번째까지 쓸때
for k in range(i,-1,-1):
s += A[k]
if max_s < s:
max_s = s
if j == 1:
dp[i][j] = max(dp[i][j], max_s)
else:
if k >= 2:
dp[i][j] = max(dp[i][j], dp[k-2][j-1] + max_s)
print(dp[n-1][m])'알고리즘 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 출발 조건이 까다로운 2차원 배열 목적지까지 이동하는 다이나믹 프로그래밍 (0) | 2025.01.27 |
|---|---|
| 무게가 실수 float인 배낭 문제에 필요한 테크닉 (0) | 2025.01.04 |
| 무한 배낭 문제 unbounded knapsack에 대한 또 다른 핵심 고찰(dp[i] = min(dp[i], dp[i-k*w[j]] + k*v[j]) = min(dp[i], dp[i-w[j]] + v[j])) (0) | 2024.12.27 |
| 원형 배열에서의 다이나믹 프로그래밍 기본 (0) | 2024.12.24 |
| 최소 편집 거리(edit distance)를 구하는 알고리즘 (0) | 2024.12.11 |
