99클럽 코테 스터디 40일차 TIL , Unique Paths

문제

풀이

m과 n이 입력으로 주어지면 오른쪽과 아래쪽으로만 움직일 수 있는 로봇이 0,0에서 출발하여 m-1, n-1에 닿는 최소의 경우가 몇인지 출력하면 되는 문제.

제출 1 - 정답

class Solution {
    
    public int uniquePaths(int m, int n) {
        int[][] grid = new int[m][n];	//그리드 생성
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i == 0 || j==0){//하나라도 0이라면 1
                    grid[i][j] = 1;
                }else{
                    grid[i][j] = grid[i-1][j] + grid[i][j-1];
                }
            }
        }

        return grid[m-1][n-1];
    }
}

 

아주 간단한 문제이다. 일단 0에서 출발하여 x나 y에 0이 포함된 곳으로 최단거리로 갈 수 있는 경우는 한 가지밖에 없다.

그리고 그 사이의 값 예를들어 1,1의 위치까지 갈 수 있는 방법은 0,1과 1,0까지 갈 수 있는 방법을 더한 것과 같다.

왜냐하면 그 위치들에서 한칸만 움직이면 되기 때문이다. 해서 좌표가 0을 포함하고 있다면 1로 넣어주고 아니라면 위와 왼쪽의 값을 더해 채워주고 마지막 칸의 값을 출력하면 된다.

TIL

• DP
• 직접써보기