출처 : 백준, https://www.acmicpc.net/problem/14494
더보기
먼저, 생각해야 할 부분
1. DP 불변의 법칙
이전 단계를 생각하자.
풀이
n, m = map(int, input().split())
map = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
map[i][j] = (map[i-1][j] + map[i-1][j-1] + map[i][j-1]) % (10e8 + 7)
print(int(map[n-1][m-1]))
2 x 2의 지도가 있다고 가정해보자. 이동 방법은 →, ↓, ↘ 세 가지 방법 밖에 없으므로
(1, 0)의 위치로 가는 방법은 ↓, (0, 1)의 위치로 가는 방법은 → 로 이동하는 방법 밖에 없다.
이를 확장하면 임의의 지도에 대해서 모든 좌측 모서리, 상단 모서리는 갈 수 있는 방법이 1가지 밖에 없다는 것을 알 수 있다.
그 외의 다른 칸들을 생각해보자.
각 칸은 모두 상, 좌상, 좌측 칸을 가지고 있고 이 칸들로부터 이동해올 수 있다.
주위의 칸에서 해당 칸으로 오는 방법은 한가지씩 밖에 없으므로
해당 칸에 도착하는 방법은 주위에 오는 칸들의 합과 같다.
즉,
map[i][j] = map[i-1][j] + map[i-1][j-1] + map[i][j-1]
#단, i != 0 and j != 0
시간 복잡도
O(N*M)
알게 된 점
파이썬의 지수 표현
10^1 = 10e0
10^9 = 10e8
파이썬의 지수 표현은 0부터 시작한다.
고찰
-
Github
'알고리즘 > Python' 카테고리의 다른 글
[python] 백준 14430 - 자원 캐기 (0) | 2022.07.10 |
---|---|
[python] 백준 10164 - 격자상의 경로 (0) | 2022.07.10 |
[python] 백준 9657 - 돌 게임3 (0) | 2022.07.10 |
[python] 백준 11051 - 이항계수 2 (0) | 2022.07.09 |
[python] 백준 11727 - 2xn 타일링 2 (0) | 2022.07.09 |