외발 뛰기 시간초과관련 질문입니다

  • ssipal5
    ssipal5

    안녕하십니까

    동적계획법으로 설계한 외발 뛰기가 계속 시간초과나옵니다...

    jump 함수를 사용해서 board[][]라는 cache에 잘 넣어줬는데 이클립스에선 yes, no 는 잘 나오지만 알고스팟 서버에 업로드하니 시간초과가 자꾸 나와요 ㅠㅠ

    소스 올릴테니 피드백 요청드립니다

    import java.util.*;

    public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int count ;
        count = sc.nextInt();
        if(count <= 50) {
            for(int i = 0; i< count ; i++) {
    
                n = sc.nextInt();
    
                square = new int[n][n];    //숫자 적혀 있는거
    
                //예제를 입력받는다
                for(int y = 0; y<n ; y++) {
                    for(int x = 0; x < n ; x++) {
                        square[y][x] = sc.nextInt();
    
                    }
                }//입력 종료
    
                board = new int[n][n];
                for(int c = 0; c < n ; c++) {
                    for(int d = 0; d < n ; d++) {
                        board[c][d] = -1;
                    }
                }
                int a = 0,b = 0;
                if(jump(b,a)>0)
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }//Test case for문
    
    
        }//if50
    
    }//main
    
    static int[][] square  = null;
    static int[][] board = null;
    static int n;
    
    private static int jump(int y, int x ) {
        //기저조건
    
        if(y >= n || x >= n ) return 0;  //범위 벗어남
        if(y == n-1 && x == n-1) return 1; //정답
    
        int ret = board[y][x];
        if(ret != -1 ) return ret;
        int jumpsize = square[y][x];
    
    
        if(  jump(y+jumpsize, x) >0 ||  jump(y, x+jumpsize) >0 )
            ret =  1;
    
            return ret ;
    
    
    }

    }

    감사합니다^^


    2달 전
1개의 댓글이 있습니다.
  • keith
    keith

    사용하신 알고리즘은 DFS(Backtracking) 인거 같습니다.
    저도 처음엔 그렇게 했는데 시간초과가 떠서, 고민해보니 Dynamic Programming으로 해결 할 수 있는 방법이 있더군요.


    2주 전 link
  • 댓글을 남기시려면 로그인하세요.