2666번 - 벽장문의 이동
ret = f(target_idx + 1, a[target_idx], y) + abs_x; ret = min(ret, f(target_idx + 1, x, a[target_idx]) + abs_y);
이 문제는 greedy 하게 풀리는 보장이 없습니다. 예를 들어서, 입력이 다음과 같이 주어진다면,
8
3 8
2
5
1
정답은 5이지만, 이 코드는 6을 출력합니다.
댓글을 작성하려면 로그인해야 합니다.
unilep 6년 전
ret = f(target_idx + 1, a[target_idx], y) + abs_x;
이런식으로 해봤습니다만ret = min(ret, f(target_idx + 1, x, a[target_idx]) + abs_y);