격자 경로 개수 세기

문제

행과 열로 이루어진 격자의 왼쪽 위 모서리에서 시작합니다. 한 번에 한 칸씩, 오른쪽 또는 아래쪽으로만 이동하여, 오른쪽 아래 모서리에 도달할 때까지 셀의 경계를 따라 이동합니다. 서로 다른 이동 순서의 개수를 세세요. 격자에는 장애물이 없습니다.

2행 3열의 격자는 정확히 2번 아래로, 3번 오른쪽으로 이동해야 합니다.

lattice_paths(rows, columns)를 구현하세요.

rows: 셀의 행 개수입니다. 꼭짓점 개수가 아닙니다.

columns: 셀의 열 개수입니다. 꼭짓점 개수가 아닙니다.

왼쪽 위에서 오른쪽 아래로 가는 경로의 개수를 반환하세요.

0 ≤ rows, columns ≤ 30 그리고 rows + columns ≤ 60. 한 쪽이 0이면 직선 경로만 존재합니다. 0 × 0 격자는 하나의 빈 경로가 있습니다. 결과는 부호 있는 64비트 정수 범위에 들어갑니다.

예시 1

입력:
rows = 2
columns = 3

예상 출력:
expected = 10

입력:
long long rows = 2;
long long columns = 3;

예상 출력:
long long expected = 10;

입력:
long rows = 2;
long columns = 3;

예상 출력:
long expected = 10;

모든 경로는 다섯 번의 이동으로 이루어집니다. 이 중 두 번을 아래로 이동하는 경우의 수는 10가지입니다.

예시 2

입력:
rows = 0
columns = 4

예상 출력:
expected = 1

입력:
long long rows = 0;
long long columns = 4;

예상 출력:
long long expected = 1;

입력:
long rows = 0;
long columns = 4;

예상 출력:
long expected = 1;

오른쪽으로 네 번 직진하는 한 가지 경로만 있습니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

각 경로는 아래로 가는 이동과 오른쪽으로 가는 이동의 순서일 뿐입니다.

힌트 2

경로를 하나씩 찾지 말고, 전체 이동 중 한 종류의 위치를 고르는 경우의 수를 세세요.

힌트 3

퇴화한 격자는 주의하세요. 한 변이 0이면 직선 경로가 정확히 1개이고, 0×0 격자도 빈 경로가 1개입니다.

예상 복잡도

시간 O(min(rows, columns)), 추가 공간 O(1)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.