scarcely   6년 전

DP 연습중인데 아래와 같은 문제를 만났습니다.

도저히 아이디어가 떠오르지 않아 고수분께 도움 요청 드립니다.


1. N개의 수열을 순서대로 M개의 그룹으로 나눈다

2. 이 때 각 그룹마다 합을 구한다

3. 결과로 나온 M개의 합에서 최대값과 최소값을 찾는다.

4. 최대값 - 최소값이 최소로 되었을 때 그 값은?

추가조건) 1번째 숫자와 M번째 숫자도 같은 그룹으로 묶일 수 있다 (원형으로 이어져 있다)


예를들어 N=4이고 M=2일 때 주어진 수열이 (1,2,3,4)라고 하면

(1) (2, 3,4)로 그룹을 나누었을 때  각 그룹의 합의 최대값-최소값은 9-1 = 8이지만

(1,2)(3,4)로 그룹을 나누면 7-3 = 4 으로 최대-최소가 더 작아지는 조합이 가능합니다.

추가조건에 의해 (1,4) (2,3)과 같은 방식으로도 그룹을 나눌 수 있으며 이 때 5-5=0으로 최소(정답)가 됩니다.

단, (1,3)(2,4)와 같은 방식으로는 순서상 이어져 있지 않기 때문에 나눌 수 없습니다.


DP로 시도해봤는데 메모이제이션이 없을 때 대략  N=30 M=15 정도가 되면 시간초과가 발생합니다.

그런데 아무리 생각해봐도 메모이제이션에 대한 아이디어가 떠오르지 않습니다 (!!)


알고리즘에 능통하신 분 DP 또는 다른 알고리즘을 이용해 풀 수 있는 힌트 부탁드립니다.

혹시 유사 문제가 백준 알고리즘에 있나요?


감사합니다.


solveit   6년 전

O(N^4M) 정도 풀이는 생각이 나는데... 문제가 실무에서 나온것 같진 않은데 N,M 크기가 어떻게 되나요?

solveit   6년 전

일단 가장 간단한 O(N^4M) 아이디어는

임의의 구간 하나를 정하고 그 구간의 합 (이 합이 T라고 하죠)이 최소 합이라고 가정합니다 (O(N^2))

원형으로 이어져 있기 때문에 이 구간을 제외한 수열에 다음과 같은 알고리즘을 생각해볼수 있습니다.

(예를 들어 1, 2, 3, 4, 5 에서 구간 (2, 3)을 고르면 이 구간을 제외한 수열은 4, 5, 1이 됩니다)

D(i, j) = 1~j번째 숫자까지 i개의 구간으로 나눴을때 (각 구간 합은 T보다 크거나 같음) 최대 합 구간과 T의 최소 차이

이 파트가 O(N^2M)으로 풀릴겁니다.

N, M <= 50 이라면 1초 안에 나올것 같기도 하네요.

scarcely   6년 전

답변 감사드립니다.

N은 40이하 M은 15정도니까 말씀하신대로 시간 안에 나올 것 같습니다.


설명이 약간 어렵게 들리는데,

O(N^4M) 알고리즘에 참고할만한 문제를 제가 풀어볼 수 있을까요?

haja   6년 전

수열에 있는 원소의 범위는 어떻게 되나요? 

scarcely   6년 전

수열 원소 범위가 그다지 크지 않다고 가정한다면 문제가 쉽게 풀릴 수 있을까요?

1<=N <=100


점화식에 대한 아이디어가 잘 떠오르지 않는데 도움 부탁드립니다.

scarcely   6년 전

해결했습니다.

힌트 주신 solveit님 감사합니다.

숫자 개수 N, 그룹 개수 M 입력

이후 N개의 숫자 입력 받아 M개의 그룹으로 나누었을 때 최대값 - 최소값을 최소로


ex>  

6 3
10 11 1000 1001 1 2
977

6개 숫자를 3개 그룹으로 나눌 때 (1, 2, 10, 11) (1000) (1001)로 나누면

1001-24 = 977이 최소값으로 출력


#include <stdio.h>

int N, M;
int a[50];
int sum[50];
int b[50];
int sum_b[50];

int d[50][22];

int maxv(int in1, int in2) {
if (in1 > in2)
return in1;
else
return in2;
}

int minv(int in1, int in2) {
if (in1 < in2)
return in1;
else
return in2;
}

int main () {
int i, j, k, l, o;
int max_1;
int min_;
int max_;
int count;
int temp;
int ans = 100000000;

scanf("%d %d", &N, &M);

max_1 = N-M+1;
sum[0] = 0;
for (i = 1; i <= N; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}

for (i = 1; i <= N; i++) {
for (j = 0; j < max_1; j++) {
if (i+j > N) {
min_ = sum[N] - sum[i-1] + sum[i+j-N];
} else {
min_ = sum[i+j] - sum[i-1];
}

count = 1;

if (i+j+1 <= N) {
for (k = i+j+1; k <= N; k++) {
b[count++] = a[k];
}
for (k = 1; k < i; k++) {
b[count++] = a[k];
}
} else {
for (k = i+j-N+1; k < i; k++) {
b[count++] = a[k];
}
}

for (k = count; k <= N; k++) {
b[k] = 0;
}

for (k = 0; k < 50; k++) {
for (l = 0; l < 22; l++) {
d[k][l] = -1;
}
}

sum_b[0] = 0;
for (k = 1; k < count; k++) {
sum_b[k] = sum_b[k-1] + b[k];
d[0][k] = 0;
if (sum_b[k] >= min_)
d[1][k] = sum_b[k];
}

for (k = 2; k < M; k++) {
for (l = k; l < count; l++) {
for (o = 1; o < count-1; o++) {
if (d[k-1][l-o] >= min_ && sum_b[l]-sum_b[l-o] >= min_) {
if (d[k][l] == -1) {
d[k][l] = maxv(d[k-1][l-o], sum_b[l]-sum_b[l-o]);
} else {
d[k][l] = minv(d[k][l], maxv(d[k-1][l-o], sum_b[l]-sum_b[l-o]));
}
}
}
}
}

if (d[M-1][count-1] > -1) {
max_ = d[M-1][count-1];
} else {
max_ = 10000000;
}

ans = minv(ans, max_-min_);
}
}

printf("%d", ans);

return 1;
}


댓글을 작성하려면 로그인해야 합니다.