[python] 백준 10164 - 격자상의 경로

출처 : 백준, https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

 

 

먼저, 생각해야 할 부분

 

-

 

---

 

풀이

 

def calcWay(start, end, map):
  s_x, s_y = start
  e_x, e_y = end

  #시작점으로부터 가로 세로 통일
  for i in range(s_x, e_x + 1):
    map[i][s_y] = map[s_x][s_y]

  for j in range(s_y, e_y + 1):
    map[s_x][j] = map[s_x][s_y]

  #합 구하기
  for i in range(s_x+1, e_x + 1):
    for j in range(s_y+1, e_y + 1):
      map[i][j] = map[i-1][j] + map[i][j-1]

  return map[e_x][e_y]

n, m, k = map(int, input().split())

map = [[1 for _ in range(m)] for _ in range(n)]

if k != 0:
  #k 위치의 좌표 구하기
  k -= 1
  
  row = k // m
  col = k % m

  calcWay((0, 0), (row, col), map)
  print(calcWay((row, col), (n-1, m-1), map))
  
else:#필수 칸이 없는 경우
  print(calcWay((0, 0), (n-1, m-1), map))

 

레퍼런스 참고

---

시간 복잡도

최악의 경우 O(N^2)

 

알게 된 점

 

-

 

고찰

 

-

 

Github

백준 10164 - 격자상의 경로

 

Reference

백준 14494 - 다이나믹이 뭐에요?