[수업]격자에서의 최단경로

Intro..

이 문제는 유명한 격자 관련 문제이다.

DP로 풀면 되니까 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

이 또한 DP로 풀면 된다.(그림그려보면 방식 자체는 간단)

dp 2차원 배열 2개를 아래형식 처럼 만들어 다뤄보면 풀 수 있다.

• wallCountArr[102][102][202] - 개수(K 카운팅)
• minWeightArr[102][102][202] - 비용(최소비용 - K 마다)

K 카운팅과 최소비용의 특징

• ‘x’ 만나면 오른쪽으로 둘다 이동 해줘야 한다.

• 즉, 한칸씩 배열 index를 ++ 해주라는 것
  => shift

• 추가로 최소 비용은 최소의 길만 택한다는점 까먹으면 안되고,
  • 추가 조건으로 동일할때 아래 경로 택하라고 했으니 왼쪽꺼를 택해야 한다.
• K카운팅은?
  • 두개 길을 둘다 더하는 형태이다.

추가로 값이 범위가 넘어가면 => % 연산자 활용

• C언어의 경우 음수로 바뀌므로 처음 계산해서 구할때부터
  %1000.... 으로 수를 잘 줄여줘서 그런 에러는 없게끔 할 것.