Baekjoon 1520, 백준 1520 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <cstdio>
using namespace std;
int M, N; int map[502][502] = {0,}; int dp[502][502] = {0,};
int func(int i, int j){
if(dp[i][j] != -1){ return dp[i][j]; }
else { dp[i][j] = 0;
if(map[i+1][j] < map[i][j] && i+1 <= M) { dp[i][j] += func(i+1, j); }
if(map[i-1][j] < map[i][j] && i-1 >= 1){ dp[i][j] += func(i-1, j); }
if(map[i][j+1] < map[i][j] && j+1 <= N){ dp[i][j] += func(i, j+1); }
if(map[i][j-1] < map[i][j] && j-1 >= 0){ dp[i][j] += func(i, j-1); } }
return dp[i][j]; }
int main() { scanf("%d %d", &M, &N);
for(int i = 1; i <= M; i++){ for(int j = 1; j <= N; j++){ scanf("%d", &map[i][j]); dp[i][j] = -1; } }
dp[M][N] = 1; int answer = func(1,1); printf("%d\n", answer); }
|
동적계획법 문제로, 새로운 아이디어가 접목되었다.
dp 배열의 값 설정을 통해
“방문 여부”를 따지는 아이디어이다.
실제로 방문 여부를 따지지 않고 코드를 짜면, 시간 초과가 발생하였다.
본 코드에서는 처음 dp 배열을 -1 로 초기화하였고, 이를 “방문하지 않았다”는 것의 여부로 사용하였다.
즉 dp != -1 이라면 이미 한 번 방문한 적이 있는 칸이라는 것이다.
특별한 조치를 하지 않는다면 전역 변수로 선언한 dp 배열은 0으로 초기화가 될 것이며,
이는 “아직 값을 계산하지 않아서 0” 인 것과, “계산을 해 보았는데 방법의 수가 0”인 것을 구별할 수 없다.
따라서 -1 을 사용하여 이를 구별하고, 시간을 줄여 준다.