hemisphere1357   1년 전

제출 번호: 98995002

https://www.acmicpc.net/source...

다른 사람들은 보통 [C, end]까지의 최솟값을 찾고자 end를 구하는 과정에서 고민을 많이 하셨던 것 같아요.

저도 질문 게시판 보고 일단 C까지만 고려한 걸 제출하고 나서 사람 수의 최댓값을 고려해야겠구나 생각했어요.

근데 다이내믹 프로그래밍을 제가 어떻게 했는지는 몰라도 C까지만 dp 테이블을 채우고 buf[N][C]의 값만 답으로 냈는데도 통과를 했습니다.

testcase.ac도 통과를 했고, AC도 받았고요.

아직 왜 되는지는 모르겠지만, 신기해서 글 써봅니다.

kolorvxl   1년 전

j - num >= 0이 아닐 때 candidate1의 값을 무한대로 설정하면 buf[i][j] = (i번째 도시까지 홍보했을 때 정확히 j명을 끌어들이는 최소 비용) 이 됩니다. 이렇게 제출하셨다면 아마 WA를 받으셨을 겁니다.

그러나 현재 j - num >= 0이 아닐 때 candidate1의 값을 cost로 설정하고 있습니다. 따라서 buf[i][j] = (i번째 도시까지 홍보했을 때 j명 이상을 끌어들이는 최소 비용) 이 됩니다. 따라서 j > C인 경우를 신경쓰지 않으셨음에도 불구하고 AC를 받으신 것 같습니다.

hemisphere1357   1년 전

어떻게 변수를 설정하냐에 따라서 결과가 천차만별로 달라지네요!

친절한 답변 감사드립니다.

다이내믹 프로그래밍 더 공부해보겠습니다.

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