JUMPGAME dp배열 초기화 값에 대해 질문합니다! fegler #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int board[105][105]; int dp[105][105]; int n; int jump(int x, int y); int main() { int c; scanf("%d", &c); for (int i = 1; i <= c; i++) { scanf("%d", &n); for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { scanf("%d", &board[a][b]); dp[a][b] = -1; //처음엔 여기를 0으로 초기화 } } if (jump(1,1)) printf("YES\n"); else printf("NO\n"); } return 0; } int jump(int x, int y) { if (x == n && y == n) return 1; if (x > n || y > n) return 0; if (dp[x][y] != -1) return dp[x][y]; dp[x][y] = (jump(x + board[x][y], y) || jump(x, y + board[x][y])); return dp[x][y]; } 제가 처음에는 dp배열에 0값으로 초기화하고 제출을 했는데 시간초과가 뜨더군요 ㅜㅜ 근데 -1으로 초기화한 후 제출해보니 맞았다고 뜨네요 원인이 너무 궁금합니다 ㅠㅠㅠ 도와주세요 ㅠ 8년 전
4개의 댓글이 있습니다. mystika jump 함수 내의 if (dp[x][y] != -1) 절에서 dp[x][y]의 값이 -1이 아니면 바로 return 하도록 되어있네요. 즉 -1을 초기값으로 본다는 것인데, 0으로 초기화하면 모든 경우에 대해 '아직 시도하지 않았다'가 아닌 '갈수없다'라고 초기화하는것이랑 똑같습니다. 8년 전 link fegler 아 저 소스는 정답소스입니다 제가 틀렸던 소스는 if(dp[x][y]!=0) 일때 return을 하고 초기 dp배열 값도 0으로 초기화를 했었습니다 그런데도 안되더군요 ㅠㅠㅠㅠㅠ 8년 전 link mystika 그 부분을 바꾸셨다고 해도 위 코드에서 dp[x][y]가 가지는 값은 결국 0과 1인데 초기값과 갈수 없다를 나타내는 값이 둘 다 0이므로 시간 초과가 나겠네요. 8년 전 link fegler 아아 그렇군요... 이상한 실수하고있었네요 답장 감사합니다!! ㅠㅠ 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
fegler
제가 처음에는 dp배열에 0값으로 초기화하고 제출을 했는데 시간초과가 뜨더군요 ㅜㅜ 근데 -1으로 초기화한 후 제출해보니 맞았다고 뜨네요 원인이 너무 궁금합니다 ㅠㅠㅠ 도와주세요 ㅠ
8년 전