글 읽기 - 두 소스의 차이점이 궁금합니다.

rain_maker 4년 전 1

값이 결정된 상태라면

재귀를 종료하고

그 값을 반환해주는 것은 둘다 같은 거 아닌가요?

//// TLE
#include <iostream>
using namespace std;
int yd[4] = { -1, 0, 1, 0 },
    xd[4] = { 0, 1, 0, -1 };
int gph[500][500];
int dp[500][500];
int n, m;
int dfs(int y, int x) {
    if (!y && !x) return 1;
    if (dp[y][x]) return dp[y][x];

    for (int i = 0; i < 4; i++) {
        int dy = y + yd[i], 
            dx = x + xd[i];
        if (dy < 0 || dy > n - 1 || dx < 0 || dx > m - 1)
            continue;
        if (gph[dy][dx] > gph[y][x])
            dp[y][x] += dfs(dy, dx);
    }
    
    return dp[y][x];
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> gph[i][j];
    
    cout << dfs(n - 1, m - 1);
    return 0;
}

//// AC
#include <iostream>
using namespace std;
int yd[4] = { -1, 0, 1, 0 },
    xd[4] = { 0, 1, 0, -1 };
int gph[500][500];
int dp[500][500];
int n, m;
int dfs(int y, int x) {
    if (!y && !x) return 1;
    
    if (dp[y][x] == -1) {
        dp[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int dy = y + yd[i], 
                dx = x + xd[i];
            if (dy < 0 || dy > n - 1 || dx < 0 || dx > m - 1)
                continue;
            if (gph[dy][dx] > gph[y][x])
                dp[y][x] += dfs(dy, dx);
        }
    }
    
    return dp[y][x];
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> gph[i][j];
            dp[i][j] = -1;
        }
    
    cout << dfs(n - 1, m - 1);
    return 0;
}

clrmt 4년 전 1

DP값이 0일 경우, 경우의 수가 0인지 아니면 값이 아직 정해지지 않아서 0인지 구분할 수 없기 때문이 아닐까요?

rain_maker 4년 전 0

저도 아는분께 말씀을 들었는데

그게 맞는 거 같습니다 ! 답변해주셔서 감사합니다 !

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 소스의 차이점이 궁금합니다.

rain_maker 4년 전 1

clrmt 4년 전 1

rain_maker 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말