bt22dr   4년 전

다이나믹 프로그래밍 2 온라인 강좌 수강중인데요. 아무리 해봐도 계속 시간 초과가 나길래 혹시나 해서 해답으로 제시된 코드를 제출해도 시간초과 나네요. 

https://gist.github.com/Baekjo...

참고로 채점번호는 6028238 입니다. 

simm4256   4년 전

dp 배열의 초기값을 0이 아닌 -1로 설정해주세요.


이유 : https://www.acmicpc.net/board/...

0으로 초기화했을 때 반례 : https://www.acmicpc.net/board/...

bt22dr   4년 전

올려주신 이유글을 봤는데요. 그러면 -1로 초기화 했을 때 dp 배열의 값이 0이 되는 경우, 그러니까 방문은 했으나 값이 0인 경우는 어떤 경우가 있을까요? 

-1로 초기화하는 목적이 단순히 방문 여부를 나타내기 위한 것이라면 -1이 아니라 -10000으로 초기화해도 동일하게 동작해야 할텐데, 정상 통과하는 코드에서 -1 초기화를 -1000으로 바꾸면 결과가 틀리다고 나오네요.

simm4256   4년 전

제가 올린 반례로 디버깅해보세요.

기존에 틀렸던 코드로 디버깅해보시면 무한루프도는 지점을 찾을 수 있습니다.

simm4256   4년 전

그리고 -10000으로 초기화해서 틀리는게 아니라 memset은 -10000으로 초기화를 해주지 못하기 때문입니다.

memset을 이용해 int 배열을 초기화할때는 0 또는 -1로 초기화합니다.

memset 자체가 문자열을 채우기 위한 함수라서 그렇습니다.

자세한 건 memset 함수를 찾아보세요.


2중 for문으로 dp배열을 -10000으로 초기화하고 돌리면 정답이 나옵니다.

bt22dr   4년 전

아, 그렇군요. 감사합니다. ^^

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