gurckddl   5년 전

고수님들 부탁드립니다! 테스트케이스도 여러개 만들어서 해봤는데 안되네요 ㅠㅠ 도와주세요!

jh05013   5년 전

이렇게 설명 하나 없이 긴 코드는 아무도 읽을 엄두를 안 낼 것입니다. 각 변수가 뭐고 무슨 식을 사용해서 풀었는지 정도는 설명해 주세요.

gurckddl   5년 전

n과 m는 각각 가로등 개수와 시작위치

D와 W는 가로등의 위치와 전력

EE[i][j][0 1] i에서 j까지를 다 껐을때의 최소전력 0일때는 i에 위치 1일 때는 j에 위치

DD는 위와 마찬가지 상황일 때 이전까지의 이동거리 입니다!

jh05013   5년 전

최적해의 부분문제가 최적일 필요는 없습니다.

5
2
1 5
2 1
3 20
4 1
100 100

마지막 가로등이 없으면 2->3->1->4가 최적이고, 있으면 2->1->3->4->100이 최적입니다.

gurckddl   5년 전

그럼 재귀함수를 통해서 모든 경우를 다 따져줘야하는건가요...?

jh05013   5년 전

물론 그렇게 하면 시간초과가 납니다.

지금 EE는 "i부터 j까지의 가로등이 낭비하는 전력"을 저장하고 있는데, 이걸 바꿔서 DD가 필요하지 않도록 해 보세요.

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