글 읽기 - 이런건 어떤 알고리즘으로 풀어야 하나요?

movie_jo 9년 전 0

DP로 풀었더니 시간초과가... 하하..ㅠㅠ

제 풀이 시간복잡도 계산해보니 N^2 나오는데 DP말곤 딱히 떠오르는 방법이 없네요

#include <stdio.h>

#define INF 2000000000
#define MIN(x,y) (x < y ? x : y)

int in[100000];

int d[100000][2];

int main (void)
{
	int N, K, i, k;

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

	for (i = 0; i < N; i++)
		scanf ("%d", &in[i]);

	N--;
	
	for (i = 0; i < N; i++)
		in[i] = in[i + 1] - in[i];

	d[0][1] = in[0];

	k = N - (K - 1)*2;

	for (i = 1; i < k; i++)
		d[i][1] = MIN (in[i], d[i - 1][1]);

	for (k = 2; k <= K; k++)
	{
		int o = k%2, x = (k + 1)%2, z = N - (K - k)*2;

		i = (k - 1)*2 - 1;
		d[i][o] = INF;

		for (i++; i < z; i++)
			d[i][o] = MIN (d[i - 1][o], d[i - 2][x] + in[i]);
	}

	printf ("%d\n", d[N - 1][K%2]);
}

h0ngjun7 9년 전 0

그리디로 해결할 수 있습니다.

Nada 9년 전 1

계속 틀려서 알고리즘이 잘못 된 줄 알았는데 구현실수군요 ㅠㅠ

연속된 세 선분을 선택했을 때 가운데가 가장 작은 길이라면

가운데 선분을 선택 안 할 경우 오른쪽, 왼쪽 선분을 무조건 선택해야 된다는

것을 이용해서 풀었습니다.

h0ngjun7 9년 전 0

저 같은 경우에는 k=n/2인 경우를 넣어보니까 구현 실수들이 전부 드러나더라구요ㅋㅋ

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

문제

문제

출처

ICPC

이런건 어떤 알고리즘으로 풀어야 하나요?

movie_jo 9년 전 0

h0ngjun7 9년 전 0

Nada 9년 전 1

h0ngjun7 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말