https://programmers.co.kr/learn/courses/30/lessons/42898
코딩테스트 연습 - 등굣길 | 프로그래머스
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매
programmers.co.kr
학교에서 모눈종이에 각 칸마다 +1 하면서 풀던 문제와 동일한 로직이다.
왼쪽 상단에서 오른쪽 하단까지 도달하는 최단거리 개수를 구하는 조건의 핵심은
1. 왼쪽 -> 오른쪽으로 이동해야 한다.
2. 위 -> 아래로 이동해야 한다.
두 가지가 있다.
점화식의 핵심은
'현재 위치까지 도달할 수 있는 경우의 수 = 현재 위치 위쪽 상단에까지 도달할 수 있는 경우의 수 + 현재 위치 오른쪽까지 도달할 수 있는 경우의 수'다.
예컨대 위 그림에서 집의 좌표가 1,1이고 2,2까지 도달하는 최단거리의 개수를 구하려면
좌표의 (2,2) = 좌표의 위쪽 상단인 (1,2) + 좌표의 오른쪽인 (2,1)
(1,1)에서 좌표 위쪽 상단인 (1,2)에 도달하는 방법은 1이고, (1,1)에서 좌표 오른쪽인 (2,1) 까지 도달하는 방법은 1개이므로
좌표 (2,2)까지 도달하는 방법은 1+1 = 2가 된다.
코드로 구현하면 아래와 같다.
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 쿠키 구입 (Level 4) (0) | 2019.11.25 |
|---|---|
| [Python] 백준 14890. 경사로 (0) | 2019.11.24 |
| [Python] 백준 14499. 주사위 굴리기 (0) | 2019.11.21 |
| [Python] 프로그래머스. 2020 카카오 recruit - 괄호 변환 (Level 2) (0) | 2019.11.20 |
| [Python] 백준 14888. 연산자 끼워넣기 (0) | 2019.11.19 |