글 읽기 - 도움 부탁드립니다

bk8540 4년 전 0

제가 어떤 부분을 놓치고 있는 걸까요?

제가 생각했을 때는 맞는것 같긴한데..

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;
const int inf = 987654321;
struct Point
{
	int x, y;
}p[10001];
int n, dp[10001];
bool cmp(Point a, Point b)
{
	if (a.x == b.x)return a.y > b.y;
	return a.x < b.x;
}
int dfs(int idx)
{
	if (idx == n)return 0;
	int&ret = dp[idx];
	if (ret != -1)return ret;
	ret = inf;
	int maxh = 0;
	for (int next = idx; next < n; ++next)
	{
		maxh = max(maxh, p[idx].y);
		int pos = p[next].x - p[idx].x;
		int cand = dfs(next + 1);
		
		ret = min(ret, max(2 * maxh, pos) + cand);
	}
	return ret;
}
int main()
{
	memset(dp, -1, sizeof(dp));

	cin >> n;
	for (int i = 0, x, y; i < n; ++i)
	{
		cin >> x >> y;

		p[i] = { x,abs(y) };
	}

	sort(p, p + n, cmp);

	cout << dfs(0) << '\n';

	return 0;
}

bk8540 4년 전 0

아 바보같이 최고높이 구할 때 next를 안쓰고 idx로써서틀렸네요 ㅠ;;후.. 역시코딩의세계란

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

문제

문제

출처

ICPC

도움 부탁드립니다

bk8540 4년 전 0

bk8540 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말