문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1832
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
프로그래머스 등굣길 문제와 비슷한 문제였습니다.
https://jaimemin.tistory.com/1938
[Programmers 코딩테스트 고득점 Kit] 등굣길
문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집.
jaimemin.tistory.com
알고리즘은 아래와 같습니다.
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 }으로 이동했을 때 경우의 수를 반환해줍니다.
#include <vector> | |
#include <cstring> | |
using namespace std; | |
const int MOD = 20170805; | |
const int MAX = 500 + 1; | |
int cache[MAX][MAX][2]; | |
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. | |
int solution(int m, int n, vector<vector<int>> city_map) { | |
memset(cache, 0, sizeof(cache)); | |
cache[1][1][0] = 1; | |
cache[1][1][1] = 1; | |
for (int i = 1; i <= m; i++) | |
{ | |
for (int j = 1; j <= n; j++) | |
{ | |
switch (city_map[i - 1][j - 1]) | |
{ | |
case 0: | |
cache[i][j][0] = (cache[i][j][0] + cache[i - 1][j][0] + cache[i][j - 1][1]) % MOD; | |
cache[i][j][1] = (cache[i][j][1] + cache[i - 1][j][0] + cache[i][j - 1][1]) % MOD; | |
break; | |
case 1: | |
cache[i][j][0] = 0; | |
cache[i][j][1] = 0; | |
break; | |
case 2: | |
cache[i][j][0] = cache[i - 1][j][0] % MOD; | |
cache[i][j][1] = cache[i][j - 1][1] % MOD; | |
break; | |
} | |
} | |
} | |
return cache[m][n][0] % MOD; | |
} |

개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 광고 삽입 (0) | 2022.07.21 |
---|---|
[Programmers] 몸짱 트레이너 라이언의 고민 (1) | 2022.07.18 |
[Programmers] 경주로 건설 (0) | 2022.07.13 |
[Programmers] 보석 쇼핑 (0) | 2022.07.09 |
[Programmers] GPS (0) | 2022.07.09 |