👀 문제
https://leetcode.com/problems/unique-paths/
👊 도전
1. 설계
- 시작점 행, 열을 1로 초기화하고 앞의 두 값을 더해가며 Finish까지 간다(초딩때 배운 길찾기 경우의수 사용).
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
*
* @author HEESOO
*
*/
class Solution {
public int uniquePaths(int m, int n) {
int[][] map=new int[m][n];
Arrays.fill(map[0], 1); // 0행 1로 초기화
for(int i=1;i<m;i++) map[i][0]=1; // 0열 1로 초기화
for(int i=1;i<m;i++){ // 값 계산
for(int j=1;j<n;j++){
map[i][j]=map[i-1][j]+map[i][j-1]; // 왼쪽과 위쪽을 더함
}
}
return map[m-1][n-1];
}
}
3. 결과
🤟 성공 🤟
처음에는 DFS로 시도했었는데, m=23, n=12에서 시간 초과가 걸렸다. DFS, BFS는 숫자가 아주 작을 때만 사용해야겠다.
4. 설명
- 배열에 합을 누적하며 Finish의 값을 찾는다
- Start의 0행, 0열을 1로 초기화하고, 나머지 값은 내 왼쪽+내 위쪽을 더한 값을 저장한다.
- m=3, n=7이면 배열은 [[1,1,1,1,1,1,1],[1,2,3,4,5,6,7],[1,3,6,10,15,21,28]]이 되고 마지막 map[m-1][n-1]의 값을 리턴하면 된다.