unilep   6년 전

문이 열려있는 곳을 x, y에 저장해두고

현재 열어야 하는 방 (a[target_idx]) 이 x또는 y에 있다면 문이 이동할 필요가 없으므로
f(target_idx + 1, x, y)

아니면 문을 움직여야 하기 때문에
x를 움직일건지 y를 움직일건지 그 중에 최소값

ret = f(target_idx + 1, a[target_idx], y) + abs_x;
ret = min(ret, f(target_idx + 1, x, a[target_idx]) + abs_y);

이런식으로 해봤습니다만
정답이 나오질 않습니다.. ㅠ

어디가 잘못된건가요?

djm03178   6년 전

이 문제는 greedy 하게 풀리는 보장이 없습니다. 예를 들어서, 입력이 다음과 같이 주어진다면,

8

3 8

2

5

1

정답은 5이지만, 이 코드는 6을 출력합니다.

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