프로그래머스 정수 삼각형

문제

나의 풀이

class Solution {
    public int solution(int[][] triangle) {
        int d[][] = new int[triangle.length][triangle.length];
        d[0][0] = triangle[0][0];
        for(int i = 1; i < triangle.length; i++) {
            for(int j = 0; j <= i; j++) {
                d[i][j] = d[i - 1][j] + triangle[i][j];
                if(j - 1 >= 0) {
                    d[i][j] = Math.max(d[i][j], d[i - 1][j - 1] + triangle[i][j]);
                }
            }
        }
        
        int answer = d[triangle.length - 1][0];
        for(int i = 0; i < triangle.length; i++) {
            answer = Math.max(answer, d[triangle.length - 1][i]);
        }
        return answer;
    }
}

앞서 풀었던 백준 정수 삼각형과 똑같은 문제이므로 직접 입력 받는 게 아니라 triangle 매개변수를 이용해서 풀면 된다.

결과

프로그래머스 등굣길

문제

나의 풀이

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        int[][] board = new int[n + 1][m + 1];
        
        for(int i = 0; i < puddles.length; i++) { // 웅덩이는 -1로 표시 
            board[puddles[i][1]][puddles[i][0]] = -1; 
        }
        
        board[1][1] = 1;
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                if(board[i][j] == -1) { 
                    continue;
                }
                if(board[i - 1][j] > 0) { // 우측 이동
                    board[i][j] += board[i - 1][j] % mod;
                }
                if(board[i][j - 1] > 0) { // 하단 이동 
                    board[i][j] += board[i][j - 1] % mod;
                }
            }
        }
        
        return board[n][m] % mod;
    }
}

결과