JUMPGAME 문제 메모이제이션 사용했음에도... 박다은 안녕하세요. 맨 처음 그저 재귀로만 백트래킹 하다가.. 시간초과가 나서 메모이제이션을 사용하고, memset함수로 캐시배열을 초기화 하였는데도 시간초과가 났습니다. 그래서 인풋을 받을 때 캐시도 같이 초기화를 해주었는데도 시간초과가 뜨네요.. 문제점이 무엇인지 알 수 있을까요? 아래는 제 소스입니다. #include<stdio.h> int map[105][105], memo[105][105]; int n; int jump(int i, int j) { if(i >= n || j >= n) return false; if(i == n-1 && j == n-1) return true; int t = memo[i][j]; if(t > 0) return t; int size = map[i][j]; return t = jump(i+size, j) || jump(i, j+size); } int main() { int testcase; scanf("%d", &testcase); while(testcase--) { scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &map[i][j]); memo[i][j] = 0; } } printf("%s\n", jump(0, 0) ? "YES" : "NO"); } } 9년 전
5개의 댓글이 있습니다. nosiar 캐시에 대입하는 부분이 없어요 9년 전 link kriii memo배열을 갱신하고 있지 않습니다. memo배열을 갱신하더라도 문제가 있는데, 0을 리턴하는 것과 아직 방문하지 않은 것의 차이를 두지 않으셨기 때문입니다. 9년 전 link 박다은 따로 변수를 생성하지 않고 메모 배열에 바로 대입하고, 메인문에서 초기화를 0이 아니라 -1로 하니까 됐네요. 답변 해주셔서 감사합니다^^ 9년 전 link cjkis 헐 사진이 바꼈네여 9년 전 link Signin 변수를 사용하는 방식으로 작성하시려면 int t = memo[i][j]; 대신에 레퍼런스 변수로 선언해서 int &t = memo[i][j]; 로 하시면 됩니다. 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
박다은
안녕하세요.
맨 처음 그저 재귀로만 백트래킹 하다가..
시간초과가 나서 메모이제이션을 사용하고, memset함수로
캐시배열을 초기화 하였는데도 시간초과가 났습니다.
그래서 인풋을 받을 때 캐시도 같이 초기화를 해주었는데도
시간초과가 뜨네요..
문제점이 무엇인지 알 수 있을까요?
아래는 제 소스입니다.
9년 전