문제 링크
https://www.acmicpc.net/problem/12785
문제 해결
1. DP[i][j] = (1, 1)에서 (i, j)까지 가는 경우의 수
2. DP[i][j] = DP[i-1][j] + DP[i][j-1]
3. a : (1, 1)부터 토스트 집의 좌표 (x, y)까지의 경우의 수
b : (x, y)부터 학교까지의 경우의 수(M, N)까지의 경우의 수 → (x, y)를 (1, 1)로, (M, N)을 (M-x+1, N-y+1)로 생각하자.
a*b가 답이된다.
주의할 점 || 생각해볼 점
1. 1,000,007로 계산할 때마다 나누어 줘야한다.
2. a와 b 모두 1,000,007이 넘지 않는다고 해도 곱하는 과정에서 넘어갈 수 있기에 long long 자료형을 사용한다.
참고
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > DP' 카테고리의 다른 글
BOJ 1038 - 감소하는 수 (0) | 2017.06.15 |
---|---|
BOJ 14585 - 사수빈탕 (0) | 2017.05.26 |
BOJ 5557 - 1학년 (0) | 2017.05.12 |
BOJ 1695 - 팰린드롬 만들기 (0) | 2017.05.02 |
BOJ 11066 - 파일 합치기 (0) | 2017.04.28 |