mic1021   8년 전

제가 첨부한 코드를 부연설명 하자면 dp[i][j]는 돌아오는 상황에서 i번째 섬에 있고 가는 길에 j번째 섬에 있는 상황일 때 모든 경우의 수를 말합니다.

가장 멀리 떨어진 섬을 max라고 하면 max값을 하나씩 증가시키는 for문이 가장 바깥에 있고 그 안에 i와 j를 0부터 max전까지 증가시키는 for문이 있습니다. 예를 들어서 dp[7][3] += dp[6][3] 이란 뜻은 7번째 섬까지 가는 경우의 수에 6번째 섬을 거쳐서 가는 경우를 더한다는 뜻입니다. 정말 여러 케이스를 넣어봤는데 다 맞게 나오거든요.. 

채점중 2%에서 멈추다가 틀렸습니다. 뜨는데 혹시 그 테스트 케이스가 뭔지 알 수 있을까요..ㅠㅠㅠ

mic1021   8년 전

60번 정도 제출해본 결과 그 이유를 찾아냈습니다.. 일단 첫번째 for문을 m<N-1이 아니라 m<N으로 고치고 맨 마지막 for문을 삭제했고. 대신  for문 안에서 m==N-1이면 나머지도 조사해서 점프가 가능하면 dp[N-1][N-1]에 해당 dp값을 추가시키는 식으로 했습니다. 그리고 for문 내부에 i와j가 같은지에 대한 조건은 없애도 상관없더군요. 어차피 dp[i][j]값을 구하지 않으니까.. 제일 중요한 개선점은 for문의 과정마다 dp값에 대한 나머지 연산을 진행해줘야 한다는 것입니다. 

p.s 제가 나중에 왜 틀린건지 까먹을까봐 적어놓은 거에요..

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