글 읽기 - 반례가 뭐가 있는지 모르겠습니다 ㅠㅠ

gktgnjftm 5년 전 0

케익을 줘야 할 위치로 이동을 하느냐,

아니면 그 인접한 위치로 이동을 하느냐, 총 5가지의 경우의 수를 가지고 진행을 하였습니다

그리고 이전좌표값을 통해서 거리를 매번 계산해줘야 하므로, 이전좌표값을 동시에 가지고 있습니다 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define INF 1000000000
#define mod 1000000007
typedef pair<ll,ll> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<int, pair<int, int>> PPP;
typedef pair<pair<double, double>, pair<double, double>> PPPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
int n;
ll dp[100005][6];
P arr[100005];
ll dist(ll x1, ll y1, ll x2, ll y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}
ll go(ll hx,ll hy,int index, int dir) {
	if (index >= n) return 0;
	ll &ret = dp[index][dir];
	if (ret != -1) return ret;
	ret = 1e14;
	ret = min(ret, go(arr[index+1].first,arr[index+1].second,index + 1, 4) + dist(hx,hy,arr[index+1].first,arr[index+1].second)); // 그 위치로 이동하는경우
	ll x = arr[index+1].first, y = arr[index+1].second;
	for (int i = 0; i < 4; i++) {
		ll nx = x + gox[i];
		ll ny = y + goy[i];
		if (nx > 100000 || ny > 100000 || nx <= 0 || ny <= 0) continue; //인접한곳이 격자판위를 벗어나는경우
		ret = min(ret, go(nx,ny,index + 1, i) + dist(hx,hy, nx, ny)); // 인접한곳으로 이동하는경우
	}
	return ret;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i <= n; i++) {
		scanf("%lld%lld", &arr[i].first, &arr[i].second);
	}
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", go(arr[0].first,arr[0].second,0, 4));
	return 0;
}

luniro 5년 전 1

문제 번호를 추가해주세요

gktgnjftm 5년 전 0

죄송합니다 ㅠㅠ 깜빡했습니다

gktgnjftm 5년 전 0

혹시 몰라서 scanf(" %lld %lld")부분으로 변경했는데 맞았습니다...

(옛날 데이터라 의심을 한번했었는데, 저 경우였던 거같습니다)

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

문제

문제

출처

ICPC

반례가 뭐가 있는지 모르겠습니다 ㅠㅠ

gktgnjftm 5년 전 0

luniro 5년 전 1

gktgnjftm 5년 전 0

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말