[Algorithm Champions] Week 4, No.1

문제

풀이

• 왼쪽 상단에서 우측 하단까지 가는 방법의 수를 구하는 문제이다.

• 우측 하단(목적지)에서 시작하여 좌측 상단(시작점)으로 올라가는 경우의 수를 셌다. (dp)

• for문으로 모든 셀들을 돈다.

  • 우측 하단(목적지)를 우선 1로 초기화를 해둔다.
  • 위로 한칸씩 가면서 해당 칸으로 갈 수 있는 방법의 수를 센다.
  • 해당 칸으로 갈 수 있는 방법의 수를 더해가면 최종 장소에는 시작점부터 목적지까지 가는 방법의 수를 구할 수 있다.

해당 칸(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];
    }
}