12785 토쟁이의 등굣길 문제 링크
문제 풀이 코드 링크
조합 계산으로 풀 수 있는… 고등학교 수학으로도 풀 수 있는 문제였으나, 모처럼 DP 태그가 있어서 DP로 풀어보았다.
토쟁이는... threw up의 그 토가 아니라, toast의 토이다. 토스트를 너무 좋아해서 토쟁이다.
토쟁이는 집에서 출발해, 토스트 집에 들려서 학교까지 등교한다. 최단 경로로 이동할 수 있는 경우의 수를 출력한다.
앞서 말했듯 조합으로도 풀 수 있는 문제이다. 출발지점부터 경유지점까지 최단 경로로 이동하는 방법에 경유지점부터 도착 지점까지 최단 경로로 이동하는 방법의 수를 곱하면 그것이 정답이다.
DP로 풀기 위해, M*N
짜리 table에서 [0, 0]
부터 [M-1, N-1]
까지의 최단 경로의 수를 구하는 함수를 만든다. 위의 그림같은 예시의 경우, 출발지점->경유지점까지는 M = 3, N = 2
로 한 번 함수를 호출하고, M = 1, N = 2
로 한 번 함수를 호출해 두 반환값을 곱하면 답이다.
DP 배열의 설계 : dp[i][j]
는 [0][0]
부터 [i][j]
까지 최단 경로로 도달할 수 있는 경우의 수. dp[M-1][N-1]
에는 최종적으로 최단 경로로 도달할 수 있는 경우의 수가 저장된다.
Bottom-up으로 문제를 풀었다. 현재 좌표에서 최단 경로로 이동할 수 있는 방향은 [i+1][j]
와 [i][j+1]
이며, 해당 값의 dp 배열에 현재 dp[i][j]
의 값을 더해준다.
import sys
input = sys.stdin.readline
W, H = map(int, input().split(" "))
X, Y = map(int, input().split(" "))
# 집->식당->학교로 이동하는 경로를 각각 집->식당, 식당->학교의 직사각형의 field로 변형.
HtoR = (Y, X) # Home to Restaurant
RtoS = (H-Y+1, W-X+1) # Restaurant to School,
# size는 (열의 수 M, 행의 수 N)로 이루어진 tuple.
# (0, 0)부터 (M-1, N-1)까지 이동하는 최단 거리의 수를 반환한다.
def countWayNUm(size) :
dp = [[0 for j in range(size[1])] for i in range(size[0])]
dp[0][0] = 1
for i in range(size[0]) :
for j in range(size[1]) :
if i + 1 < size[0] :
dp[i+1][j] += dp[i][j]
if j + 1 < size[1] :
dp[i][j+1] += dp[i][j]
return dp[size[0]-1][size[1]-1]
wayToR = countWayNUm(HtoR)
wayToS = countWayNUm(RtoS)
print((wayToR * wayToS) % 1000007)