[ BOJ 백준 1520번 - 내리막 길 ] 해설 및 코드

https://www.acmicpc.net/problem/1520

 

목적

지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하자.

 

접근법

1. 메모이제이션 기법을 이용하여 상하좌우 인접한 지점의 경우의 수를 계산하자.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int m, n, a[500][500], s[500][500], di[] = { 0,0,1,-1 }, dj[] = { 1,-1,0,0 };
 
int sol(int i, int j){
    int& ref = s[i][j];
    if (ref != -1)return ref;
 
    ref = 0;
    f(d, 0, 4) {
        int ni = i + di[d], nj = j + dj[d];
        if (ni < 0 || nj < 0 || ni >= m || nj >= n || a[ni][nj] >= a[i][j])continue;
        ref += sol(ni, nj);
    }
    return ref;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(s, -1, sizeof(s));
    cin >> m >> n;
    f(i, 0, m)f(j, 0, n)cin >> a[i][j];
    s[m - 1][n - 1] = 1;
    cout << sol(0, 0);
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.