[BOJ] 12785 토쟁이의 등굣길

thoho·2023년 1월 16일
0

코딩 문제 풀이

목록 보기
8/13

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) 
profile
어떻게든 굴러가고 있는

0개의 댓글