[Programmers] 보행자 천국

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1832

프로그래머스

프로그래머스 등굣길 문제와 비슷한 문제였습니다.

https://jaimemin.tistory.com/1938

[Programmers 코딩테스트 고득점 Kit] 등굣길

 

알고리즘은 아래와 같습니다.

1. 좌표와 함께 방향도 고려해야 하므로 cache 배열을 [y 좌표][x 좌표][방향] 이렇게 삼차원 배열로 선언해줍니다.

1.1 city_map은 0-index 배열이고 선언한 cache 배열은 1-index 배열입니다.

1.2 따라서, cache 배열의 y좌표는 [1, m], x좌표는 [1, n]을 범위로 잡고 city_map 배열의 y 좌표는 [0, m - 1], x 좌표는 [0, n-1]로 잡았습니다.

1.3 정리를 하자면 cache[y][x][dir] = i라고 한다면 { y - 1, x - 1 } 좌표에서 dir 방향으로 이동할 때 해당 경우의 수는 i 가지입니다. (cache는 1-index)

2. 차가 오른쪽, 아래쪽으로만 움직일 수 있으므로 우리는 두 방향만 체크해주면 됩니다.

2.1 현재 칸이 0일 경우 왼쪽에서 오는 차와, 위에서 오는 케이스를 합산해줍니다.

2.2 현재 칸이 1일 경우 통행이 금지되어 있으므로 0

2.3 현재 칸이 2일 경우 방향을 꺾을 수 없으므로 이전 칸의 경우의 수와 동일합니다.

3. cache[m][n][0] 혹은 cache[m][n][1]를 반환하여 { 0, 0 }에서 { m, n }으로 이동했을 때 경우의 수를 반환해줍니다.

 

 

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~