왼쪽 상단에서 우측 하단까지 가는 방법의 수를 구하는 문제이다.
우측 하단(목적지)에서 시작하여 좌측 상단(시작점)으로 올라가는 경우의 수를 셌다. (dp)
for문으로 모든 셀들을 돈다.
해당 칸(x,y)으로 갈 수 있는 방법의 수 = 아래 칸(x,y+1)으로 갈 수 있는 방법의 수 + 오른쪽 칸(x+1,y)으로 갈 수 있는 방법의 수
package com.company.w4;
/*
date; 21.07.08
21:50 ~ 22:19
input: two positive integers - width, height -> rectangular grid
output: integer - 왼쪽 상단에서 우측 하단까지 갈 수 있는 방법의 수
constraints:
down or right
width * height >= 2 (1,2) or (2,1) -> 최소 두 칸의 표 생성됨
1 <= width = height <= 10
edge cases:
width * height = 2 -> return 1
1. 가로*세로 이차원 배열 생성
2. 해당 칸에 갈 수 있는 방법의 수를 저장한다.
3. 해당 칸에 도달할 수 있는 다른 칸이 ? 맞닿은 칸이 있다면 그 칸들의 합을 현재 칸에 넣는다.
- -
| 3 | 1 |
- -
| 2 | 1 |
- -
| 1 | 1 |
- -
4. (0,0) 칸의 값을 반환
2 & 3 -> for
time: O(width*height)
space: O(width*height)
*/
public class No1 {
public static void main(String[] args) {
int width = 2;
int height = 3;
System.out.println(numbersOfWays(width, height));
}
// time: O(w * h), space: O(w * h)
public static int numbersOfWays(int width, int height) {
// base case
if (width * height == 2) return 1;
int[][] waysArray = new int[width][height];
for (int i = width - 1; i >= 0; i--) {
for (int j = height - 1; j >= 0; j--) {
if (i == width - 1 && j == height - 1) {
waysArray[i][j] = 1;
continue;
}
// 오른쪽 표가 존재할 경우
if (i + 1 < width) {
waysArray[i][j] += waysArray[i + 1][j];
}
// 아래쪽 표가 존재할 경우
if (j + 1 < height) {
waysArray[i][j] += waysArray[i][j + 1];
}
}
}
return waysArray[0][0];
}
}