문제
접근 방법
그냥 완전탐색으로 문제를 풀 경우 시간 초과가 났다. 따라서 중간 중간 메모이제이션을 활용해 값을 저장했다.
코드
#include <iostream> #include <algorithm> #include <cstring> using namespace std; int N; int map[100][100]; long long int dp[100][100]; long long int dfs(int r, int c) { // 범위 밖 if(r < 0 || c < 0 || r >= N || c >= N) return 0; // 이전 방문 여부 if(dp[r][c] > 0) { return dp[r][c]; } // 도착지 if(r == N - 1 && c == N - 1) { dp[r][c] = 1; return dp[r][c]; } // 길 x if(map[r][c] == 0) { return 0; } // 두 가지의 경우를 더해서 저장 long long int num = dfs(r + map[r][c], c) + dfs(r, c + map[r][c]); // 메모이제이션 dp[r][c] = num; return dp[r][c]; } int main() { cin >> N; for(int i = 0; i < N; i ++) { for(int j = 0; j < N; j ++) { cin >> map[i][j]; } } memset(dp, 0, sizeof(dp)); cout << dfs(0, 0); return 0; }