[코드트리] 2차원 최대 증가 수열

문제링크

문제

n * m의 숫자가 적혀있는 사각형에서 1,1에서 조건을 만족하여 밟을 수 있는 칸의 수의 최대를 구하시오.

• 지금 밟은 칸보다 큰 수만 밟을 수 있다.
• 지금 칸의 위치에서 최소 한 칸 오른쪽, 아래를 밟을 수 있다. (x, y -> x + 1, y + 1)

문제 풀이 과정

• int[][] dp를 만들어서 0,0에서부터 조건에 만족하는 경우에 값을 갱신

문제 풀이 코드

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        grid = new int[n][m];
        dp = new int[n][m];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }

        dp[0][0] = 1;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                for (int x = 0; x < i; x++){
                    for (int y = 0; y < j; y++){
                        if (dp[x][y] == -1)
                            continue;
                        
                        if (grid[i][j] > grid[x][y]) // 밟을 수 있는 경우
                            dp[i][j] = Math.max(dp[x][y] + 1, dp[i][j]);
                    }
                }
            }
        }

        max = 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
                max = Math.max(max, dp[i][j]);
        }

        System.out.print(max);

    }